FindAllNumbersDisappearedInAnArrayOPT [source code]

public class FindAllNumbersDisappearedInAnArrayOPT {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<Integer>();
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if (nums[index] > 0) {
                nums[index] = - nums[index];
            }
        }

        for(int j = 1 ;j <= nums.length ; j++){
            if(nums[j - 1] > 0){
                result.add(j);
            }
        }
        return result;        
    }

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

看了一下跑的最快的几个代码, 大体思路都跟我这个是类似的. 所以估计就是代码细节上的波动造成的速度差异, 这个就不纠结了. 所以基本上是没有什么提速空间了;

这个代码完成了in place. 还是一个妹子做出来的. 这是作者本人的解释:
Think we surely have to negate anytime we are given an array with values from 1 to the length of array. If anyone has a better idea, will be happy to hear.
The steps followed in this is:

1. Negate each number while traversing
2. Run again and find the index that is not negated.

题外话: 这里要注意一个特点, 这里前面给了一个条件就是 1 ≤ a[i] ≤ n (n = size of array), 这个条件如果敏感一点的话, 可以知道很可能就是故意让你用value as index的技术(as in Counting Sort), what's more, 这个value as index的过程很可能还可以直接in place完成(因为值域大小等于 array 长度);

虽然这个代码不算快, 但是完成了in place的任务. 背后的思考也是很巧妙的, 很厉害.
注意的一点是, 这个算法就算是某些 number 出现超过两次, 也都可以搞定, 因为if (nums[index] > 0)这个判断把所有第二次开始以及以后的 occurence 全都无视了;

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