P137 缺失的所有数字

描述#

这个题目说的是，给你一个大小为 n 的整数数组，数组中的数字都大于等于 1 并且小于等于 n。你要找出 1 ~ n 这 n 个数字中，没有出现在数组里的数字。

比如说，给你的数组是：
1, 1, 4, 2, 4, 6
这个数组的长度是 6，因此你要返回 1 ~ 6 这 6 个数字里，没有在数组中出现的数字，也就是 [3, 5]。

代码#

public class AlgoCasts {

  // Time: O(n), Space: O(n)
  public List<Integer> findDisappearedNumbers(int[] nums) {
    if (nums == null || nums.length == 0) return Collections.emptyList();
    List<Integer> result = new ArrayList<>();
    boolean[] existed = new boolean[nums.length];
    for (int num: nums) existed[num-1] = true;
    for (int i = 0; i < existed.length; ++i)
      if (!existed[i])
        result.add(i+1);
    return result;
  }

  // Time: O(n), Space: O(1)
  public List<Integer> findDisappearedNumbersO1(int[] nums) {
    if (nums == null || nums.length == 0) return Collections.emptyList();
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < nums.length; ++i) {
      int idx = Math.abs(nums[i]) - 1;
      if (nums[idx] > 0) nums[idx] = -nums[idx];
    }
    for (int i = 0; i < nums.length; ++i)
      if (nums[i] > 0)
        result.add(i+1);
    return result;
  }

}