自定义哈希算法充分利用原数组空间

题目链接-来源：力扣（LeetCode）

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

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3

思路：

假设不限制空间复杂度，本题显然可以用普通的哈希表存储所有元素，然后从 1 开始遍历正整数，直到找到第一个不发生冲突的正整数即为答案。
现在要求 O(1) 空间复杂度，我们考虑如何充分利用原数组空间，螺蛳壳里做道场。
我们总共有 n 个元素，并且有长度为 n 的数组空间，并且 n 个元素当中，会有 /[0,n] 个元素或者小于等于 0、或者大于 n（n 个不相同的正整数若均小于等于 n，则最小未出现的元素为 n + 1， 否则，答案一定在 (0,n]之间），不在我们考虑之列，也就是说，我们的数组空间是完全够用的，经过充分的交换之后，可以把所有处于 (0,n] 之间的元素哈希到合适的位置上。（理论上，这里有无数种哈希算法，比如 Hash(x) = (x + a) % n，a 为任意整数。但我们只需任选一种，取最直观最方便的， Hash(x) = x - 1）
现在我们确定了哈希算法，只需遍历数组中每个元素 x，跳过不符合要求的元素，只关注在 (0,n] 当中的元素，我们将其交换到其哈希值(x - 1)对应的下标所在的位置。对于交换后的元素，我们仍要判断其是否应当交换，直到某次交换后的元素不符合要求位置。
细节：由于数组中可能有重复元素，交换前需要检查一下目标位置的元素是否已经是正确元素，若正确则不需要交换。若不进行检查，会陷入死循环。
虽然我们不知道具体应当进行多少次交换，但可知每次交换时，我们都将一个正确元素摆到了相应位置，而数组中最多有 n 个正确元素，因此最坏情况下要进行 n 次交换，均摊时间复杂度为 O(n)。
时间复杂度：O(n)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1);
            }
            
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        
        return len + 1;
    }
    
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}