原地哈希法(41,442,448)

た入场券 2022-10-29 14:28 108阅读 0赞

### 某些类型的题目希望我们在解题时找到重复出现或是缺失的那个数却不让我们使用额外空间,这意味着我们无法使用额外的哈希表来统计数字出现的次数 ###

### 比如下面这道题目:442 ###

给定一个整数数组 a，其中1 ≤ a\[i\] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。

找到所有出现两次的元素。

你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？

示例：

输入:  
\[4,3,2,7,8,2,3,1\]

输出:  
\[2,3\]

### 我们在遍历这个数组的过程中,首先把每个数字其真正对应位置上的数字取反 ###

### 比如4如果作为索引的话对应位置的数字为7,那么我们把7取反为-7,然后依次类推遍历数组 ###

### 如果某个位置的数字在遍历的过程中由负数又转为正数了,那么说明这个数字重复出现了 ###

class Solution {
    public:
        vector<int> findDuplicates(vector<int>& nums) {
             //原地哈希算法
             vector<int> res;
             for(int i = 0; i < nums.size();++i){
                 int p = abs(nums[i])-1;
                 nums[p] *= -1;
                 if(nums[p] > 0) res.push_back(abs(nums[i]));
             }
             return res;
        }
    };

### 448: ###

给定一个范围在 1 ≤ a\[i\] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。

找到所有在 \[1, n\] 范围之间没有出现在数组中的数字。

### 这道题的做法和上一道的做法类似:把每个数对应位置上的数取反,这次的不同点是只变为负数而不再变回来,最后为正的的数的索引即为消失的数字 ###

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

### 41: ###

给你一个未排序的整数数组 `nums` ，请你找出其中没有出现的最小的正整数。

### 这题的思路和上两题是差不多的,只不过我们换一种哈希思路,把每一个数换到其索引对应的位置上去,最后判断每个数和其位置是否一一对应,如果不对应,则说明这个数字没有出现过 ###

class Solution {
    public:
        int firstMissingPositive(vector<int>& nums) {
            int n = nums.size();
            for(int i = 0; i < nums.size(); ++i){  //把所有元素放到对应的位置上去
                while(nums[i] > 0 && nums[i] < n  && 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) return i+1;
            }
            return n+1;
        }
    };