LeetCode——Find All Numbers Disappeared in an Array

Question

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]

Solution

用hash table求解。

Answer

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        map<int, int> dict;
        for (int i : nums)
            dict[i]++;
        vector<int> res;
        for (int i = 1; i <= nums.size(); i++)
            if (dict[i] == 0)
                res.push_back(i);
        return res;
    }
};
           

時間複雜度O(2n)。 網上給出了另外一種解答：

The idea is very similar to problem 442. Find All Duplicates in an Array: https://leetcode.com/problems/find-all-duplicates-in-an-array/.

First iteration to negate values at position whose equal to values appear in array. Second iteration to collect all position whose value is positive, which are the missing values. Complexity is O(n) Time and O(1) space.

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int len = nums.size();
        for(int i=0; i<len; i++) {
            int m = abs(nums[i])-1; // index start from 0
            nums[m] = nums[m]>0 ? -nums[m] : nums[m];
        }
        vector<int> res;
        for(int i = 0; i<len; i++) {
            if(nums[i] > 0) res.push_back(i+1);
        }
        return res;
    }
};
           

它的意思是數組中有這個數，那麼對應位置的數就會變成負的，如果數組中缺失某個數，那麼這個數對應位置的數最後就是正的。是以，凡是最後為正的數的位置都是缺失的數。

轉載于:https://www.cnblogs.com/zhonghuasong/p/6658609.html