448. Find All Numbers Disappeared in an Array

印度阿三17 2020-01-29

展开全文

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]

解题思路：

参考了https:///problems/find-all-numbers-disappeared-in-an-array/discuss/481254/C++-solution-O(1)-Easy-7-lines-code

巧妙的改变数组本身的值。遍历整个数组，将数组的值作为索引，将对应索引位置的数组值变为负数，这样遍历一遍后，数组值为正的那个索引，比如nums[5] = 2, 则说明5没有出现过。在实际的应用中，如果数组的值可以随便改变，则可以使用此方法。

class Solution{
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> rlt;
        for(int i=0; i<nums.size(); i  ) {
            nums[abs(nums[i])-1] = -abs(nums[abs(nums[i])-1]);
        }
        for(int i=0; i<nums.size(); i  ) {
            if(nums[i]>0) {
                rlt.push_back(i 1);
            }
         }
        return rlt;
    }
};