FindAllNumbersDisappearedInAnArrayOPT2 [source code]

public class FindAllNumbersDisappearedInAnArrayOPT2 {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
                int tmp = nums[i];
                nums[i] = nums[tmp - 1];
                nums[tmp - 1] = tmp;
            }
        }
        List<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                res.add(i + 1);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        FindAllNumbersDisappearedInAnArrayOPT2 tester = new FindAllNumbersDisappearedInAnArrayOPT2();
        int[] input1 = {4,3,2,7,8,2,3,1};
        for (int i : tester.findDisappearedNumbers(input1)) System.out.println(i);
    }
}

这个是另外一个完成了 inplace 的代码, 速度跟之前那个差不多;

这个是作者的解释:
The idea is simple, if nums[i] != i + 1 and nums[i] != nums[nums[i] - 1], then we swap nums[i] with nums[nums[i] - 1],
for example, nums[0] = 4 and nums[3] = 7, then we swap nums[0] with nums[3]. So In the end the array will be sorted and if
nums[i] != i + 1, then i + 1 is missing.
The example run as follows

[4,3,2,7,8,2,3,1]
[7,3,2,4,8,2,3,1]
[3,3,2,4,8,2,7,1]
[2,3,3,4,8,2,7,1]
[3,2,3,4,8,2,7,1]
[3,2,3,4,1,2,7,8]
[1,2,3,4,3,2,7,8]
Since every swap we put at least one number to its correct position, the time is O(n);

如果不好理解的话, 可以理解为invariant 是each nums[i] is stored on position nums[i]-1 (as long as it appears in nums);

这个算法是对于 1 ≤ a[i] ≤ n (n = size of array) 这个条件的林一种思路的利用. 反正类似于前面那个取相反数的思路,最后完成的就是要在nums 里面完成一个visited的信息的保存;

Problem Description

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]
Subscribe to see which companies asked this question.

Hide Tags Array
Hide Similar Problems (H) First Missing Positive