用已有空间构建哈希表

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

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

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

示例 1：

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

思路：

本题题目要求空间复杂度为 O(1)，如果不限制空间复杂度，只要将大小满足 [1, n] 区间内的数组元素存入哈希表。再遍历 [1, n] 区间，第一个不在哈希表中的整数即为所求答案。

考虑空间复杂度为常数，如果仍要使用哈希表的方法，我们只能考虑利用数组原有的空间。
由于我们只需定位 [1, n] 区间内的每个元素，而数组长度恰为 n，因此我们只需实现一种 [1, n] 到 数组下标[0, n - 1] 一一对应的映射方法作为我们的哈希算法。这里为了简便起见，可以令 hash(x) = x - 1。
接着我们考虑遍历数组，将 [1, n] 范围内的元素全部交换到哈希算法对应的下标位置；而对这个范围以外的元素，我们只需跳过不作考虑即可。
显然，交换后的元素仍可能处于 [1, n] 范围内，我们需要循环地重复交换，直到当前的元素不在 [1, n] 范围内。当然，如果当前元素和欲交换位置所在的元素相同，就会陷入死循环，所以循环停止条件还要判定这两个元素是否相等。
可以证明，不论我们进行了多少次循环的交换，最终我们操作的次数一定在 O(n) 范围，因为每一次交换，我们都至少将 1 个（至多 2 个）元素，摆放到了相应的位置，而元素个数是有限的。
交换完毕后，我们仍然遍历整个数组，第一个 nums[i] != i + 1 的元素，对应的 i + 1 即为我们所求整数，否则，所求整数就是整个数组之后的第一个整数，即 n + 1。

时间复杂度：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;
    }
}