Find All Numbers Disappeared in an Array

题目链接

传送门

题目大意

给一个长度为n的数组,数组元素范围1~n,求1~n中未出现在给定数组中的数字

解题思路

最开始的想法就是用set集合记录下数组中出现的元素,然后遍历1~n,求未出现的元素;
上面这种解法时间复杂度O(n),空间复杂度O(n)。

优化:

遍历给定数组,将每个元素对应下标的数组值置为负数;
接下来遍历1~n,若数组值大于0,则未出现过。
时间复杂度O(n),空间复杂度O(1)

参考代码

// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int length = nums.size();
        set<int> setN;
        for (int index = 0; index < length; index ++) {
            setN.insert(nums[index]);
        }
        vector<int> ret;
        for (int index = 1; index <= length; index ++) {
            if (!setN.count(index)) {
                ret.push_back(index);
            }
        }
        return ret;
    }
};
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int length = nums.size();
        for (int i = 0; i < length; i ++) {
            int index = abs(nums[i]) - 1;
            nums[index] = (nums[index] > 0) ? -nums[index] : nums[index];
        }

        vector<int> ret;
        for (int index = 0; index < length; index ++) {
            if (0 < nums[index]) {
                ret.push_back(index + 1);
            }
        }
        return ret;
    }
};

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

© 2018-2019 惜春令 京ICP备18010644号 网站地图