442. Find All Duplicates in an Array & 448. Find All Numbers Disappeared in an Array

442. Find All Duplicates in an Array

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

My Solutions:

Use index positions as the "real" numbers. To indicate visited, make it negative. Second time you see negative number means a duplicate so add to list.

把nums里的数字当做index，再把index上的数字变成负数。所以如果碰到一个负数的数字，说明这个数曾经被转换过， 把此数加入list

e.g.[1,2,3,1]

i = 0, index = 1; nums[0] > 0, nums: [-1,2,3,1]

i = 1, index = 2; nums[1] > 0, nums: [-1,-2,3,1]

i = 2, index = 3; nums[2] > 0, nums: [-1,-2,-3,1]

i = 3, index = 1; nums[0] < 0, newList.add(1)

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        
        List<Integer> newList = new ArrayList<Integer>();     // creating a new List
        for(int i = 0; i < nums.length; i++){  
            int index = Math.abs(nums[i]); // Taking the absolute value to find index
            if (nums[index - 1] > 0){ 
                nums[index - 1] = -nums[index - 1];
            } else{ // If it is not greater than 0 (i.e) negative then the number is a duplicate
                newList.add(Math.abs(nums[i])); 
            }
        }
        return newList;
    }
}

448. Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

和上题类似，先把所有数字对应的index上的数字变成负数。再循环一遍，没有被变过的数就是没有出现过的数，将此数加入结果

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new ArrayList<>();
        
        for (int i = 0; i < nums.length; i++) {
            int val = Math.abs(nums[i]) - 1;
            if (nums[val] > 0) nums[val] = -nums[val]; 
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) list.add(i + 1);
        }
        return list;
    }
}