中山企业推广网站制作/怎么优化自己网站

今天是母亲节，祝全天下的母亲节日快乐。
本文首发于馆主君晓的博客，05-08

题目内容

  442. 数组中重复的数据，题目截图如下：

题目分析

  这个题目第一眼一般就能够想到使用哈希表来做，还是老步骤。我们先来转述下题目的意思，题目是说，给你一个长度为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;}
};

代码实现

  代码实现如上所示。

结语

  父母在，不远游，游必有方。