Subject requirements

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]

There is an array of integers in which all elements are between 1 and N, where n is the length of the array. Some elements appear once, and some elements appear twice. Find all the numbers in the array that appear twice.

Idea 1: Exchange

In order to find all the numbers that appear twice in the O(N) time, the core requirement is to use the existing array to record the elements that have been accessed without losing the elements that have not been accessed. Idea 1 adopts the core idea of exchange, that is, exchange the value on the current subscript and the value on the position with the value as the subscript every time. If the value on the subscript position of the value is equal to it, it means that the number has been traversed once.

The code is as follows:

    public List<Integer> findDuplicates(int[] nums) {
        int index = 0;
        List<Integer> result = new ArrayList<Integer>();
        while(index < nums.length) {
            int num = nums[index];
            if(num == 0){
                index++;
            }else if (nums[num-1] == num) {
                if(index != num-1){
                    result.add(num);
                    nums[index] = 0;
                }
                index++;
            }else{
                swap(index, num-1, nums);
            }
        }
        return result;
    }
    
    public void swap(int i, int j, int[] nums) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

Idea 2: take the opposite

Is there a way to keep the value of nums[i] in the current position and record whether i+1 has been accessed in some way? You can record whether or not you have been accessed by using the reverse method. If you access the value on the position with index I, judge whether the value on the position of nums[nums[i]-1] is negative. If yes, it means that num[i] appears twice. Otherwise, reverse the value on the position of nums[nums[i]-1.

The code is as follows:

    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            int index = Math.abs(nums[i])-1;
            if (nums[index] < 0)
                res.add(Math.abs(index+1));
            nums[index] = -nums[index];
        }
        return res;
    }