Leaky Cauldron
0%

原地哈希

Posted on Edited on

概念

将数组视为哈希表，哈希函数为数组元素与数组索引之间的映射。

例题 1(剑指 offer #03)

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
 [2, 3, 1, 0, 2, 5, 3]
输出： 2 或 3

限制：

2 <= n <= 100000

题解

将数组中各元素放至与与元素值相等的索引处（即将数组视为哈希表，哈希函数为 f(nums[i]) = nums[i]），在交换过程中若发现目标位置已有满足条件的值则说明遇到了重复：

当遍历至 4 位置处的 2 时发现目标位置已有 2，说明 2 发生了重复。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findRepeatNumber(int[] nums) {
        int tmp;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                if (nums[i] == nums[nums[i]]) return nums[i];
            }
            tmp = nums[i];
            nums[i] = nums[tmp];
            nums[tmp] = tmp;
        }

        return -1;
    }
}

例题 2 (LeetCode #41)

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

示例 1:

输入: [1, 2, 0]
输出: 3

示例 2:

输入: [3, 4, -1, 1]
输出: 2

示例 3:

输入: [7, 8, 9, 11, 12]
输出: 1

提示：

你的算法的时间复杂度应为 O(n) ，并且只能使用常数级别的额外空间。

题解

本题难在限制了时间复杂度为 O(n) 且常数级别的额外空间，利用排序算法时间复杂度最低为 O(logn) ，不符合条件。

由题意可知，输出的范围为 [1, n + 1] ，将数组视为哈希函数为 f(nums[i]) = nums[i] - 1 的哈希表将数组重新排布。再遍历数组并判断各元素是否满足 nums[i] == i + 1 的对应关系，若不满足则数组中未出现的最小整数为 i + 1 ，若数组中元素全部满足条件则最小整数即为数组长度加 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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[i] != nums[nums[i] - 1])
                swap(i, nums[i] - 1, nums);
        }

        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) return i + 1;
        }

        return len + 1;
    }

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