Monday, August 7, 2017

[Leetcode] Find All Numbers Disappeared in an Array, Solution

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]
[Thoughts]
题目里面其实提示复用已有的returned list,所以对数字做一遍统计,把缺失的数字放到returned list的尾部,在返回结果前,把原数组中的数字清除掉即可。


[Code]
1:    vector<int> findDisappearedNumbers(vector<int>& nums) {  
2:      vector<int> result(nums.size(), 0);  
3:        
4:      for(int i =0; i< nums.size(); i++) {  
5:        result[nums[i]-1] = 1;  
6:      }  
7:        
8:      for(int i =0; i< nums.size(); i++) {  
9:        if(result[i] == 0) {  
10:          result.push_back(i+1);  
11:        }  
12:      }  
13:        
14:      result.erase(result.begin(), result.begin() + nums.size());  
15:      return result;  
16:    }  



No comments: