[LeetCode] 448. Find All Numbers Disappeared in an Array

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]

找到所有数组中消失的数字。影子题442。题意也几乎一样。

注意这个题的范围也是从1到N，所以才能用442题的解法。442题是把遇到的数字当成坐标，去把对应坐标上的数字改成负数，如果再次遇到，则说明是重复数字；这个题的做法也是把遇到的数字当成坐标，把坐标映射到的数字改成负数，再遍历第二遍的时候，如果发觉某个数字没有被改成负数则说明第一次没有被遍历到，也说明他对应的index是缺失的。

时间O(n)

空间O(1) - required

Java实现

 1 class Solution {
 2     public List<Integer> findDisappearedNumbers(int[] nums) {
 3         List<Integer> res = new ArrayList<>();
 4         for (int i = 0; i < nums.length; i++) {
 5             int index = Math.abs(nums[i]) - 1;
 6             if (nums[index] > 0) {
 7                 nums[index] = -nums[index];
 8             }
 9         }
10         for (int i = 0; i < nums.length; i++) {
11             if (nums[i] > 0) {
12                 res.add(i + 1);
13             }
14         }
15         return res;
16     }
17 }