448. Find All Numbers Disappeared in an Array

Posted on | In |

LeetCode 448. Find All Numbers Disappeared in an Array

按照题意，要在不使用额外空间的情况下得出结果。那么我们的基本思路是，用好题目已给的空间，也就是作为参数传入的数组的空间。我们要对这个数组添加额外的信息，同时还要保证数组原有的信息可以被正确分离。

最简单的想法是：

  • 遍历整个数组，对于数组中的每个元素a，将数组中下标为a的元素置为负。那么在第二次遍历整个数组时，如果数组中某个元素的值不为负，那么这个元素的下标就没有出现过，也就符合题目给出的条件。

考虑到数组下标从0开始，而数组元素的范围是从1开始，我们重新描述一下两次遍历的过程。

  • 第一次遍历，对于数组中每一个下标为i的元素，我们将nums[nums[i] - 1]置为它对应的负值。

  • 第二次遍历，对于数组中每一个下标为i的元素，如果nums[i]不为负值，那么将i + 1加入到结果数组中。

代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<Integer> findDisappearedNumbers(int[] nums) {
    List<Integer> result = new LinkedList<Integer>();
    for (int i = 0; i < nums.length; i++) {
        int idx = Math.abs(nums[i]) - 1;
        nums[idx] = -Math.abs(nums[idx]);
    }
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            result.add(i + 1);   
        }
    }
    return result;
}