数组原地哈西一类题一网打尽

目录

 一.数组中重复的数据

 二.找到数组中所有消失的数字

 三.缺少的第一个正数

 四.寻找重复数

---

一.数组中重复的数据

1.letecode链接：

442. 数组中重复的数据 - 力扣（LeetCode）

2.题目描述：

3.解题思路：

1.由于题目说了所有的整数的范围在这个[1,n]当中所以我们将数组当中的数字调整成nums[i]=i+1这样的形式由于这个数组当中有出现两次的数字那么肯定有一些位置的数字不满足nums[i]=i+1这样的形式，如果不满足说明当前位置的数字一定是这个重复的。

2.那么如何将数组中的元素调整成nums[i]=i+1这种形式了，比如说我们当前来到的位置他所对应的值为val并不满足nums[i]=i+1此时当前位置的值要去的地方应该是val-1位置，所以我们只需要将这两个位置的数进行交互就可以了

4.对应代码：

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        if(nums.empty())return{};
         
         int i=0;
         int N=nums.size();
         vector<int>ans;
         while(i
         {
             if(nums[i]==i+1)//当前位置上放的数本身就是正确的
             {
                 i++;
                 continue;
             }
             else
             {
                 if(nums[nums[i]-1]==nums[i]){
                   //注意不能再这里收集答案否则会重复收集因为有可能其它的数把你给怼出来
                     i++;
                 }
                 else{
                     swap(nums[nums[i]-1],nums[i]);
                 }
             }
         }
         for(int i=0;i
         {
             if(nums[i]!=i+1)
             {
                 ans.push_back(nums[i]);
             }
         }
        return ans;
    }
};

 二.找到数组中所有消失的数字

1.对应letecode链接：

448. 找到所有数组中消失的数字 - 力扣（LeetCode）

2.题目描述：

3.解题思路：

1.本题的解题思路和上题基本一模一样也是根据他给定范围是在[1,N],我们将将数组中的数组的形式可以搞成nums[i]=i+1，调整完成之后我们再一次遍历数组如果nums[i]!=i+1那么此时i+1就是消失的数字。

4.对应代码：

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
            int N=nums.size();
            for(int i=0;i
            {
                Helper(nums,i);
            }
            vector<int>ans;
            for(int i=0;i
            {
                if(nums[i]!=i+1)
                {
                    ans.push_back(i+1);
                }
            }
            return ans;
    }
    void Helper(vector<int>&nums,int i)
    {
           while(nums[i]!=i+1)
           {
               int tmp=nums[i];
               //如果发现自己要去的那个位置已经有人在了停止循环否则会进入死循环当中
               if(nums[i]==nums[tmp-1]){
                   break;
               }
               swap(nums[tmp-1],nums[i]);
               
           }
    }
};

 三.缺少的第一个正数

1.对应letecode链接

41. 缺失的第一个正数 - 力扣（LeetCode）

2.题目描述：

 

3.解题思路：

本题的思路和前面两题的思路也是一样的，我们希望将数组当中的每个位置调整成nums[i]=i+1这样的形式，但是这个本题可能有负数并且数组可能超过了数组的长度这该如何了，如果我们发现某个位置的数值小于0或者大于了数值的长度这个位置的数字我们不做任何处理，对于一个位置上的数nums[i]他应该去的位置是nums[i]-1，所以我们只需要判断每个位置的i对于nums[i]==nums[nums[i]-1]是否成立如果成立说明本来就在正确的位置上我们不需要进行调整，如果发现不满足条件那么我们只需要将nums[i]位置和nums[nums[i]-1]位置的数进行交互，继续重复上面的步骤直到不满足条件或者到了正确的位置

下面我们来看看图解：

 

 4.对应代码：

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
         
         int N=nums.size();
         for(int i=0;i
         {
             //由于是正数所以必须要大于0
              while(nums[i]>0&&nums[i]-1])
              {
                  //nums[i]应该去的位置是nums[i]-1
                  swap(nums[i],nums[nums[i]-1]);
              }
         }
         for(int i=0;i
         {
             if(nums[i]!=i+1)//不满足nums[i]=i+1那么i+1就是第一个缺少的正数
             {
                 return i+1;
             }
         }
         //走到这里说明给定的数组每个位置都满足nums[i]=i+1那么缺失的第一个正数应该是N+1
         return N+1;
    }
};

四.寻找重复数

1.对应letecode链接：

287. 寻找重复数 - 力扣（LeetCode）

2.题目描述：

3.解题思路：

本题虽然可以使用上面的解法将数组调整成nums[i]=i+1的形式但是题目做了限制不允许我们修改数组，而是采用这个快慢指针的方式来解，本人觉得这种解法很难想到。

首先明确前提，整数的数组 nums 中的数字范围是 [1,n]。考虑一下两种情况：

如果数组中没有重复的数，以数组 [1,3,4,2]为例，我们将数组下标 n 和数 nums[n] 建立一个映射关系 f(n)f(n)，
其映射关系 n->f(n)为：
0->1
1->3
2->4
3->2
我们从下标为 0 出发，根据 f(n)f(n) 计算出一个值，以这个值为新的下标，再用这个函数计算，以此类推，直到下标超界。这样可以产生一个类似链表一样的序列。
0->1->3->2->4->nullptr

如果数组中有重复的数，以数组 [1,3,4,2,2] 为例,我们将数组下标 n 和数 nums[n] 建立一个映射关系 f(n)f(n)，
其映射关系 n->f(n) 为：
0->1
1->3
2->4
3->2
4->2
同样的，我们从下标为 0 出发，根据 f(n)f(n) 计算出一个值，以这个值为新的下标，再用这个函数计算，以此类推产生一个类似链表一样的序列。
0->1->3->2->4->2->4->2->……
这里 2->4 是一个循环，那么这个链表可以抽象为下图：

 此时问题就转换为了求一个环形链表的入环节点，如果不清楚的话可以参考我的链表博客

在链表中我们来到下一个节点是slow=slow->next而在这里就是slow=nums[slow]

4.对应代码

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
          int slow=nums[0];
          int fast=nums[nums[0]];
          while(fast!=slow){
              slow=nums[slow];
              fast=nums[nums[fast]];//一次走两步
          }
          //
          
          fast=0;
          while(slow!=fast){
              fast=nums[fast];
              slow=nums[slow];
          }
          return slow;
    }
};