Find All Numbers Disappeared in an Array

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/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.

Input:

[4,3,2,7,8,2,3,1]

Output:

[5,6]

Thoughts

不让用额外的space并且要O(N)时间, 必须要利用i和nums[i]的关系. 如果一个不缺, nums[i]里存的应该是i+1. 所以可以把nums[nums[i] - 1]做特殊标记, 这样当重新遍历到i时看到标记就能知道i + 1出现过. 那么如何做标记呢? 刚开始想把nums[nums[i] - 1]存为0, 但这么做有个问题, 比如[2,1], 会变成[2, 0], 那就不知道1出现过了. 有种比较巧妙的方法既能保留标记又能保留原index, 即取负数. 比如[2,1, 2]变成[-2, -1, 2], 那我们就能知道1和2对应的i = 0和1时出现过, 但3对应的2没出现过.

Code

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

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                res.add(i + 1);
            }
        }

        return res;
    }
}

Analysis

时间复杂度O(N), 空间O(1).