了解原地哈希思路，使用其解决LC几道代表性题目。

原地哈希

概念学习

我个人对原地哈希的理解：

原地：一般题干要求O(1)的空间复杂度，此时我们可以考虑使用入参数组，在不开辟多余空间的情况操作，就是就地、原地算法；
哈希：hashmap是我们大多数时候使用哈希数据结构的一种通用实现，内部也是使用了数组进行存储，部分题干中的数据，有比较明确的哈希映射关系，比如[1,n]数据，可以直接存放在n长度的数组中，对应哈希函数：hash(x)=x-1；

可以参考下liweiwei大佬的讲解：原地哈希（哈希函数为：f(nums[i]) = nums[i] - 1）。

本文接下来通过LC上的几道题来感受、理解其特征、运用。

题目

剑指 Offer 03. 数组中重复的数字

这道题之前写过题解：数组中重复的数字原地部分有序化题解。

思路

原地哈希解法的核心就是：

识别题干已知条件
- 数据范围：[0,n-1]
- 有数字是重复出现的
- 返回任意一个重复数字

尝试使用原地哈希的思路，我们尝试把遍历到的每个数据都放到对应位置：nums[nums[i]]=nums[i]。

这种操作重复，重复数据一定会相遇：如果此时nums[i]下标处已经有归位的数据，说明找到了重复数据。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


    public int findRepeatNumber(int[] nums) {
        int n = nums.length;
        // 尝试把遍历到的数字放到 i 的位置上，进行局部有序化
        // 如果往过放的过程，发现i的位置已经存在了i数值，说明重复，即可返回
        // i指向前序已经归位的下一个下标
        int i=0;
        while(true){
            while(nums[i]!=i){
                if(nums[nums[i]]==nums[i]){
                    return nums[i];
                }
                swap(nums,i,nums[i]);
            }
            i++;
        }
    }

    public void swap(int[] nums,int i1,int i2){
        int tmp=nums[i1];
        nums[i1]=nums[i2];
        nums[i2]=tmp;
    }

442. 数组中重复的数据

思路

分析题干：

数据量n，数据范围[1, n]
需要找出所有重复数据

我们尝试用解上道题的套路来处理：

遍历数组，将数据nums[i]放在下标nums[i]-1处
收集所有nums[i]!=i+1的数据

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


public List<Integer> findDuplicates(int[] nums) {
    List<Integer> ans= new ArrayList<>();
    int n=nums.length;
    for(int i=0;i<n;i++){
        while(nums[nums[i]-1]!=nums[i]){
            swap(nums,i,nums[i]-1);
        }
    }
    for(int i=0;i<n;i++){
        if(nums[i]!=i+1){
            ans.add(nums[i]);
        }
    }
    return ans;
}

private void swap(int[] nums, int i1, int i2){
    int tmp=nums[i1];
    nums[i1]=nums[i2];
    nums[i2]=tmp;
}

参考下官解的做法：

将遍历到的数据对应下标值设置为相反数（一个数既表达了访问状态，也保留了原值）
下次碰到对应下标为负数时，说明是重复元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


    /**
     * 当前值对应下标，访问过后，我们将其设置为相反数，表示已经被访问
     * 下次碰到重复值，发现对应下标值已经是负数，将其相反数塞进ans
     * <p>
     * 时间复杂度 O(n)
     * 空间复杂度 O(1)
     */
    public List<Integer> findDuplicates(int[] nums) {
        // 访问过的数字，在对应下标处标记为负数相反数
        List<Integer> ans = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int curr = Math.abs(nums[i]);
            if (nums[curr - 1] < 0) {
                ans.add(curr);
            } else {
                nums[curr - 1] = -nums[curr - 1];
            }
        }
        return ans;
    }

448. 找到所有数组中消失的数字

思路

分析题干：

数据量n，数据范围[1, n]
题目要求出没出现的数字

同样的套路，我们遍历数组，将nums[i]都归位到nums[i]-1下标处。

再遍历一次，i+1!=nums[i]的就是消失的数字。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


/**
 * 原地hash，使用入参数组，进行数据还原。
 * 题干限定了数据范围为 [1,n]，尝试将当前下标的数替换到对应下标上，nums[i]下标对应：nums[i]-1
 * 碰到下标 nums[i]-1 处 与当前值相同时，进行下一个下标处理
 * <p>
 * 最终，遍历整个数组，下标处值不等于 i+1 的，即为缺失的数据
 * <p>
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

public List<Integer> findDisappearedNumbers(int[] nums) {
    List<Integer> ans = new ArrayList<>();
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        // 当前位置值与下标不匹配，同时 nums[i]-1 下标处于当前值不等
        // nums[i] != i + 1 &&
        while (nums[nums[i] - 1] != nums[i]) {
            swap(nums, i, nums[i] - 1);
        }
    }

    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            ans.add(i + 1);
        }
    }
    return ans;
}

private void swap(int[] nums, int i1, int i2) {
    int tmp = nums[i1];
    nums[i1] = nums[i2];
    nums[i2] = tmp;
}

41. 缺失的第一个正数

思路

观察用例：

[1,2,0]
- 将[1,n]范围的数据放到nums[i]-1的位置上
- 遍历到的第一个nums[i]!=i+1的即为所求
[1,2,3]
- 遍历完数组，此时n+1即为所求
[3,4,-1,1]
- 归位之后：[1,-1,3,4]
- -1即为所求
[7,8,9,11,12]
- 所有数据均不在[1,n]范围内
- 直接从1遍历，1即为所求

算法过程：

将 nums[i]-1 有效下标范围的数据归位，即 x放在 x-1 的位置上，负数、0、大于n的数我们不动
依次从1开始遍历，没有归位的i值，即为缺失的最小正数

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */
public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        while (nums[i] - 1 >= 0 && nums[i] - 1 < n && nums[nums[i] - 1] != nums[i]) {
            swap(nums, i, nums[i] - 1);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (nums[i - 1] != i) {
            return i;
        }
    }
    return n + 1;
}

private void swap(int[] nums, int i1, int i2) {
    int tmp = nums[i1];
    nums[i1] = nums[i2];
    nums[i2] = tmp;
}

小结

原地哈希的固定套路：

使用已有的数组空间
根据数据特征来映射数据到数组中

找重复：

先归位
归位重复的即为重复项

找缺失：

先归位（根据题干适当检查数据范围）
nums[i]!=i+1的即为缺失项

原地哈希#

概念学习#

题目#

剑指 Offer 03. 数组中重复的数字#

思路#

代码#

442. 数组中重复的数据#

思路#

代码#

448. 找到所有数组中消失的数字#

思路#

代码#

41. 缺失的第一个正数#

思路#

代码#

小结#

原地哈希的固定套路：#

找重复：#

找缺失：#