特殊哈希表-原地哈希

例题一

链接：41.缺失的第一个正数

题解

一种简单的方法是利用map，但是空间复杂度不符合条件；另一种简单的方法是直接排序，但是时间复杂度不符合条件。于是我们结合两者，提出一种算法，姑且称之为·原地哈希·。该算法是基于比较的排序，不需要额外的空间：给定长度为N的数组，我们想将其变换为这样一个形式：[1,2,3,...,N]，但是实际上肯定会有部分数是错误的，每一个错误的位置就代表了一个缺失的正数。以题目中的示例二 [3, 4, -1, 1] 为例，恢复后的数组应当为 [1, -1, 3, 4]，我们就可以知道缺失的数为2。
我们可以对数组进行一次遍历，对于遍历到的数 \(x=nums[i]\) ，如果 \(x∈[1,N]\) ，我们就知道 \(x\) 应当出现在数组中的 \(x−1\) 的位置，因此交换 \(nums[i]\) 和 \(nums[x−1]\) ，这样 \(x\) 就出现在了正确的位置。在完成交换后，新的 \(nums[i]\) 可能还在 [1,N] 的范围内，我们需要继续进行交换操作，直到 \(x∉[1,N]\)。此外，如果 \(nums[x - 1]=nums[i]\)，就说明已经处于正确的位置，因此不必交换。
代码如下：

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

例题二

链接：287.寻找重复数

题解

该题与上一题一样，也采用原地哈希的方法，代码如下：

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