C++编程练习题：找出数组中所有重复的元素

学编程

题意, 有一个N大小的数组, 数组里的数字在1到N之间, 有些数字出现2次, 有些数字出现1次. 请找出所有出现2次的数字. 要求时间复杂度是O(N) 空间复杂度是 O(1).

如果不考虑空间复杂度, 那么我们可以开一个O(n) 的哈希表来记录数字是否已经出现过了, 在C++里我们可以用 unordered_set 集合来实现 O(1) 的查找和插入.

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> r;
        unordered_set<int> hash;
        for (const auto &n: nums) {
            if (hash.count(n)) {  // 已经出现过了
                r.push_back(n);
            } else {
                hash.insert(n);  // 添加到集合中
            }
        }
        return r;
    }
};

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> r;
        unordered_set<int> hash;
        for (const auto &n: nums) {
            if (hash.count(n)) {  // 已经出现过了
                r.push_back(n);
            } else {
                hash.insert(n);  // 添加到集合中
            }
        }
        return r;
    }
};

因为数字的范围是在1到N 之间, 所以我们可以把相应数字坐标的元素给取反, 如果本来已经是负数了, 就代表这个数字的绝对值已经出现过了.

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> r;
        for (auto i = 0; i < nums.size(); ++ i) {
            if (nums[abs(nums[i]) - 1] < 0) { // 已经出现过了
                r.push_back(abs(nums[i]));
            } else {
                nums[abs(nums[i]) - 1] = -nums[abs(nums[i]) - 1];
            }
        }
        return r;
    }
};

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> r;
        for (auto i = 0; i < nums.size(); ++ i) {
            if (nums[abs(nums[i]) - 1] < 0) { // 已经出现过了
                r.push_back(abs(nums[i]));
            } else {
                nums[abs(nums[i]) - 1] = -nums[abs(nums[i]) - 1];
            }
        }
        return r;
    }
};

这样就不需要额外的空间, 并且时间复杂度也是 O(n).

英文: C++ Coding Exercise – Find All Duplicates in an Array

GD Star Rating
loading...

本文一共 217 个汉字, 你数一下对不对.

C++编程练习题: 找出数组中所有重复的元素. (AMP 移动加速版本)
上一篇: C++编程练习题: 找出字符串的所有大小小组合
下一篇: 入佳能 6D Mark II 入门级全幅单反

赞赏我的几个理由.

¥ 打赏支持

扫描二维码，分享本文到微信朋友圈