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]

解法2：原地修改

遍历数组，每次检查一个元素。对于每个输入元素nums[i]，标记nums[nums[i] - 1]为负数，表示nums[i]出现过。第二遍遍历数组，若nums[i] < 0，说明i + 1出现过，否则说明i+1没有出现过。