原地哈希

问题描述

假设有一个长度$n$的数组，所有数字都在 $0～ n-1$ 的范围内。数组中某些数字可能是重复的，这时要我们找出数组中其中一个重复的数字，且时间复杂度 $O(n)$，空间复杂度为常数，此时应该怎么实现呢？

---

一般而言，对于这样的问题，通常想法是排序或者用一个Map进行存储，但是这样都会违背时间或空间复杂度的要求，所以出现了”原地哈希“的思想

算法思路

容易知道，对于长度$n$的数组，所有数字都在 $0～ n-1$ 的范围内时，如果没有重复元素，那么数组的索引和值将会是一对一的关系。也就是说，重复的元素导致了一对多的映射关系。

因此，可以遍历数组，将索引和值进行尽可能多的一一对应映射，即使得 $nums[i] = i$。这样，相当于在原数组上进行了一个Map映射，也就是原地哈希名称的由来。

实现代码

public int findRepeatNumber(int[] nums) {
    int i = 0;
    int n = nums.length;
    while(i < n) {
        if(nums[i] == i) {
            i++;
            continue;
        }
        if(nums[nums[i]] == nums[i]) return nums[i];
        swap(nums,i,nums[i]);
    }
    return -1;
}

public void swap(int[] nums, int i , int j){
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

推广

由上面的算法思路，我们可以知道，如果数组索引和值的映射关系并非一一对应时，运用上述算法我们便可以推广到找数组中重复或缺失的元素

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

上述题目中对于每一个索引 $i$，经过元素换位后，索引$i$对应的正整数值 $i+1$ 若出现在数组中，一定已经换位到索引$i$处，其余的索引值要么为非正数，要么大于数组长度$n$。

总之，找到第一个 $nums[j]≠ j+1$ 位置处即为所要找的数组中最小的未出现过的正整数对应的索引，对应的数值为$j+1$

代码实现

public int firstMissingPositive(int[] nums) {
	int n = nums.length;
    int i = 0;
    while(i < n){
        if(nums[i] <= 0 || nums[i] > n || nums[nums[i] - 1] == nums[i]){
            i++;
            continue;
        }
        swap(nums,i,nums[i]-1);
    }
    i = 0;
    while(i < n){
        if(nums[i] != i+1){
            return i+1;
        }
        i++;
    }
    return n+1; //此时也就是这n个数正好是1~n，所以最小未出现的正整数即为n+1
}

public void swap(int[] nums, int i , int j){
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}