原地哈希算法

2022年12月31日 · 214 字 · 2 分钟

原地哈希算法(Cyclic Sort)主要应用在值都在$[0,n]$的数组$nums$中，此时可以将$nums[i]$作为索引，放回原数组，当然，由于程序上索引是从0开始，因此可以将$nums[i]$放到$nums[nums[i]-1]$的位置上。

举例

Leetcode 268. 丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：

输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 3：

输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。

示例 4：

输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。

提示：

  • n == nums.length
  • 1 <= n <= 104
  • 0 <= nums[i] <= n
  • nums 中的所有数字都 独一无二

**进阶：**你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

解答

用哈希表可以解答，但是空间复杂度达到了$O(n)$，没有利用到值都在$[0,n]$这个已知条件。所以我们用原地哈希解答本题。

  1. 遍历数组，如果$nums[i]-1>=0$ 且$nums[i] != nums[nums[i]-1]$，证明$nums[i]$未归位，我们将$i$和$nums[i]-1$处的数字交换，此步骤要一直循环到$nums[i]-1$越界或者$nums[i]$归位
  2. 重新遍历数组，如果$nums[i] != i+1$，证明当前位置的$nums[i]$是错的，也就是缺少本来应该放到这个位置的数字，所以答案也就呼之欲出了。
class Solution {

        // 原地哈希
        // 1. 将nums[i] 放到 nums[nums[i]-1]的位置
        // 2. 重新遍历，如果 nums[i] != i+1 则缺失i+1数字
        public int missingNumber(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                // 数字归位
                // 如nums[i]为2，那么最终需要放到1号索引
                while (nums[i] - 1 >= 0 && nums[i] != nums[nums[i] - 1]) {
                    swap(nums, i, nums[i] - 1);
                }
            }
            // 数字已归位，查询哪个数字的值和位置不匹配，不匹配的就是缺失的数字
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != i + 1) {
                    return i + 1;
                }
            }
            return 0;
        }

        private void swap(int[] nums, int i, int j) {
            var temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
}

时间复杂度：$O(n)$。$n$是数组长度，每个元素会被一次性移动归位，此后不再移动，因此每个元素的访问次数是常数，而总共需要访问$n$个数字。

空间复杂度：$O(1)$。复用题目给定的$nums$空间作为哈希表，未引入额外空间。

qrcode