448. Find All Numbers Disappeared in an Array _numbers

博观而约取，厚积而薄发。这篇文章主要讲述448. Find All Numbers Disappeared in an Array相关的知识，希望能为你提供帮助。
p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 14.0px "Helvetica Neue"; color: #323333 } p.p2 { margin: 0.0px 0.0px 0.0px 0.0px; font: 13.0px Menlo; color: #323333; background-color: #f5f5f5 } p.p3 { margin: 0.0px 0.0px 0.0px 0.0px; font: 13.0px Menlo; color: #323333; background-color: #f5f5f5; min-height: 15.0px } span.s1 { }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]
【448. Find All Numbers Disappeared in an Array】
Output:
[5,6]

idea: It‘s hard to solve without extra space and in O(n) without the condition 1 ≤ a[i] ≤ n.
Solution 1: for the number a[a[i]-1], if it is positive, assign it to its opposite number, else unchange it. The logic is if i+1 appear in the array, a[i] will be negative, so if a[i] is positive, i+1 doesn‘t appear in the array.

1 class Solution { 2 public: 3vector< int> findDisappearedNumbers(vector< int> & nums) { 4vector< int> res; 5for (int i=0; i< nums.size(); i++){ 6int idx=abs(nums[i])-1; 7nums[idx]=(nums[idx]> 0)?(-nums[idx]):nums[idx]; 8} 9for (int i=0; i< nums.size(); i++){ 10if (nums[i]> 0) res.push_back(i+1); 11} 12return res; 13} 14 };

Solution 2: move nums[i] from positon i to its right position nums[i]-1, swap nums[i] and nums[nums[i]-1]. Finally, if i doesn‘t equal nums[i]-1, means i+1 doesn‘t appear in the array. Note the line 6-8

1 class Solution { 2 public: 3vector< int> findDisappearedNumbers(vector< int> & nums) { 4vector< int> res; 5for (int i=0; i< nums.size(); i++){ 6if (nums[i]!=nums[nums[i]-1]){ 7swap(nums[i],nums[nums[i]-1]); 8--i; 9} 10} 11for (int i=0; i< nums.size(); i++){ 12if (i!=nums[i]-1){ 13res.push_back(i+1); 14} 15} 16return res; 17} 18 };

Solution 3: add nums[nums[i]-1] to n, use (nums[i]-1)%n to avoid the overflow of nums[i]-1. Finally, if nums[i]< =n, i+1 is the disappeard number.

1 class Solution { 2 public: 3vector< int> findDisappearedNumbers(vector< int> & nums) { 4vector< int> res; 5int size=nums.size(); 6for (int i=0; i< size; i++){ 7nums[(nums[i]-1)%size]+=size; //mod to avoid overflow 8} 9for (int i=0; i< size; i++){ 10if (nums[i]< =size){ 11res.push_back(i+1); 12} 13} 14return res; 15} 16 };