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]
题目大意:
给定一个数组，这个数组的长度是n，其中的元素是1～n，因为其中有一些元素重复出现，所以1～n会有一些元素没有出现在数组中，题目要求找出这些数。
1:最直接的想法是我们把每个元素都归位，即元素1放在第一个位置（数组下标为0）。元素2放在第二个位置（数组小标为1），以此类推。归位以后，遍历数组，找出不对应的地方输出即可。
2:我们这里有一个技巧。不去归位，就可以轻松的找到“缺失”的元素。
具体是这样操作的，遍历数组的每个元素，例如第一个元素是5，位置5上的元素是8，那么我们把8变成-8，表示有元素可以归到这个位置，那么当我们遍历完整个数组后，没有变成负数的元素的位置就表示没有元素可以归到这个位置。自然我们就知道了“缺失”的元素。
题目代码:
class Solution {
public:vector<int> findDisappearedNumbers(vector<int>& nums) {vector<int>ans;int i = 0; while(i < nums.size()){if(nums[i] != nums[nums[i]-1])swap(nums[i], nums[nums[i]-1]);elsei++;}for(int i = 0; i < nums.size(); i++){if(nums[i] != i+1)ans.push_back(i+1);}return ans;}
};class Solution {
public:vector<int> findDisappearedNumbers(vector<int>& nums) {vector<int>ans;for(int i = 0; i < nums.size(); i++){int id = abs(nums[i]) - 1;nums[id] = nums[id] > 0 ? -nums[id] : nums[id];}for(int i = 0; i < nums.size(); i++){if(nums[i] > 0)ans.push_back(i+1);}return ans;}
};