哈哈哈希冲突的妙用

点击上方蓝字设为星标哈哈哈希冲突的妙用

下面开始今天的学习~

哈哈哈希冲突的妙用

大家好,我是程序员吴师兄。

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题03. 数组中重复的数字

题目链接:https://www.algomooc.com

一、题目描述

找出数组中重复的数字。

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

示例 1:

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

限制:

<= n <= 100000

二、题目解析

注意题目描述:一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的 范围内,这个 范围 恰好与数组的下标可以一一对应。

所以我们可以执行某种操作,使索引与值一一对应即索引 0 的值为 0,索引 1 的值为 1。而一旦某个索引的值不只一个,则找到了重复的数字,也即发生了 哈希冲突

三、动画描述

四、图片描述

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

哈哈哈希冲突的妙用

五、参考代码

class Solution {
    public int findRepeatNumber(int[] nums) {
        //设索引初始值为 i = 0
        int i = 0;
        //遍历整个数组 nums 
        while(i < nums.length) {
            //索引 i 的值为 i,无需执行交换操作,查看下一位
            if(nums[i] == i) {
                i++;
                continue;
            }
            //索引 nums[i] 处的值也为 nums[i],即找到一组相同值,返回 nums[i] 即可
            if(nums[nums[i]] == nums[i]) return nums[i];
            //执行交换操作,目的是为了使索引与值一一对应,即索引 0 的值为 0,索引 1 的值为 1
            int tmp = nums[i];
            nums[i] = nums[tmp];
            nums[tmp] = tmp;
        }
        //如果遍历整个数组都没有找到相同的值,返回 -1
        return -1;
    }
}

六、复杂度分析

时间复杂度

遍历数组需要 O(N) 时间。

注意参考代码里面的关键字 continue,这表示在 while 的一次循环里面,只有这次循环将 索引(i)索引值(num[i]) 匹配到了,才会执行下一次循环。

在每一次的循环过程中,索引(i)索引值(num[i]) 匹配到后,在后续的循环过程中不会操作它们,所以虽然一开始的循环过程中,执行的交换操作较多,但在后续的循环过程中根本不需要再执行操作了。

根据均摊复杂度分析 ,总的时间复杂度为  O(N) ,N 为数组的长度。

空间复杂度

使用常数复杂度的额外空间,为  O(1)

七、相关标签

  • 数组

  • 哈希

  • 原地哈希


我还会在以下平台发布内容

GitHub 知乎