442.数组中重复的数据

链接：442.数组中重复的数据
难度：Medium
标签：数组、哈希表
简介：给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。

题解 1 - cpp

• 编辑时间：2022-05-08
• 执行用时：80ms
• 内存消耗：43.5MB
• 编程语言：cpp
• 解法介绍：哈希存储。

class Solution {
   public:
    vector<int> findDuplicates(vector<int>& nums) {
        unordered_set<int> s;
        vector<int> ans;
        for (auto& num : nums) {
            if (s.count(num))
                ans.push_back(num);
            else
                s.insert(num);
        }
        return ans;
    }
};

题解 2 - cpp

• 编辑时间：2022-05-08
• 执行用时：24ms
• 内存消耗：32.7MB
• 编程语言：cpp
• 解法介绍：遍历，与对应索引的位置进行交换，如果索引上已存在说明重复。

class Solution {
   public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ans;
        for (int i = 0; i < nums.size(); i++) {
            while (nums[i] != nums[nums[i] - 1])
                swap(nums[i], nums[nums[i] - 1]);
        }
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != i + 1) ans.push_back(nums[i]);
        }
        return ans;
    }
};

题解 3 - cpp

• 编辑时间：2022-05-08
• 执行用时：48ms
• 内存消耗：32.7MB
• 编程语言：cpp
• 解法介绍：遍历，对应位置取负。

class Solution {
   public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ans;
        for (int i = 0; i < nums.size(); i++) {
            int num = abs(nums[i]);
            if (nums[num - 1] < 0)
                ans.push_back(num);
            else
                nums[num - 1] *= -1;
        }
        return ans;
    }
};