【05-08】力扣每日一题

今天是母亲节，祝全天下的母亲节日快乐

题目内容

题目分析

这个题目第一眼一般就能够想到使用哈希表来做，还是老步骤。我们先来转述下题目的意思，题目是说，给你一个长度为n的整数数组，并且数组里的所有整数都在范围[1,n]之间，并且每个整数要么出现一次，要么出现两次，然后你需要找出出现两次的数字，并且将其返回。

思路一，使用c++的unordered_map，我们只需要使用一次循环，循环遍历数组，将数组的元素作为key放在map里，如果key已经存在了那么久将其放入结果数组中，循环结束，我们的元素也就找出来了。

class Solution {
private:
    unordered_map<int,int> map;
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int n = nums.size();
        vector<int> res;
        for(int i = 0;i<n;i++){
            if(map.find(nums[i])!=map.end()){
                map[nums[i]]+=1;
                res.push_back(nums[i]);
            }else{
                map[nums[i]] = 1;
            }
        }
        return res;
    }
};

但是上面的思路耗时太久，我们可以尝试第二种思路，首先排序然后使用双指针，按照升序的方式进行排序，之后一前一后指针，如果两个指针所指的元素相等，那么就将元素放入结果数组。

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        // 排序+双指针
        vector<int> res;
        int n = nums.size();
        if(n==1){
            return res;
        }
        sort(nums.begin(),nums.end());
        int back = 0,front = 1;
        while(front<n){
            if(nums[back]==nums[front]){
                res.push_back(nums[back]);
            }
            back++;
            front++;
        }
        return res;
    }
};

上面的思路的确可以，但是其实不符合题目要求，题目要求时间复杂度为o(n)，空间复杂度为常数。于是就有了下面的第三种方式，原地哈希。直接看代码可能比较好懂：

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        // 原地数组
        vector<int> res;
        int n = nums.size();
        if(n==1){
            // 特殊处理
            return res;
        }
        for(int i = 0;i<n;i++){
            // 获取nums[i]的绝对值 因为可能为负数 负数是因为我们取反了
            int x = abs(nums[i]);
            if(nums[x-1]>0){
                // 下标所处位置的元素大于0 说明还没被取负 取负的都是我们第一次碰见的数
                nums[x-1] =-nums[x-1];
            }else{
                // 已经取负了 所以现在这次相当于第二次碰见这个数 那么就加入结果数组
                res.push_back(x);
            }
        }
        return res;
    }
};