当前位置:网站首页>剑指 offer 面试题精选图解 03 . 数组中重复的数字(超详细超容易理解的动画解法!!!)...

剑指 offer 面试题精选图解 03 . 数组中重复的数字(超详细超容易理解的动画解法!!!)...

2021-03-24 22:22:14 程序员吴师兄

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

题目链接:剑指 offer 面试题精选图解 03 . 数组中重复的数字(超详细超容易理解的动画解法!!!)

一、题目描述

找出数组中重复的数字。

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

示例 1:

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

限制:

2 <= n <= 100000

二、题目解析

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

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

三、动画描述

四、图片描述


v2-a9617925a1fbad00acf2d41198085c3a_b.jpg



v2-b5b7d28c610e7afb05374bd1c5260958_b.jpg



v2-eab27993c8d397395867db7bfe8fd3de_b.jpg



v2-e7ef18ef40606a0973ee16a842a94f35_b.jpg



v2-fc9ff7176f11bbf4353ce1f0e33c9061_b.jpg



v2-00ac030a9e15131c8613c001673cc9ef_b.jpg



v2-1f25bcb7e67a171f759c759f2b9b2534_b.jpg



v2-c9d51c5f2d400159fe509a24fb03a92c_b.jpg



v2-f5652972b5a6e854bd1782104169a8d6_b.jpg



v2-7d00b9116fb93a9729fae12787d2f0c1_b.jpg



v2-70effe556489fd92a1adf4f9ad7f61f5_b.jpg



v2-8f62add09931b073b4709b8dec2269ad_b.jpg



v2-ba96f0715703269f3dcc0bb6bfeda692_b.jpg



v2-d2be4423413e3b902c37e37700b366f7_b.jpg



v2-fb7c02a82e47adc6c7b873185d0f00f7_b.jpg



v2-85210bb381b9e4f3354deb4c8523903e_b.jpg



v2-1ec0b3591807f3e9445d5e7cb0becc75_b.jpg



v2-c429da770fca674b31b31743a59d1b65_b.jpg



v2-c429f8b4633a5ae78cdd6e835476051a_b.jpg



v2-00ac030a9e15131c8613c001673cc9ef_b.jpg



v2-160f3a955772a8350ee3c170a411e6e7_b.jpg



v2-f09b5ec9d1b0dfea0d8196347cc7ca5b_b.jpg



v2-9bc8c85c40bf37734417cbee6dbb3da1_b.jpg



v2-c74d3a8bbdabc3b4b62f519c2139b249_b.jpg



v2-3245d78229cfb7ca3fcd937dfda50510_b.jpg



v2-08b89c2a3404cfec73c46713dab70ba4_b.jpg



v2-eef03d0da22ce606afdb2a7ca47ec7fb_b.jpg



v2-a0cb41e0b369a7a8fdc2feddd93ccff5_b.jpg



v2-bba362868923b28c431803fb6528fc19_b.jpg



v2-3af5458d89ee0e285df72a6275565080_b.jpg


五、参考代码

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)

七、相关标签

  • 数组
  • 哈希
  • 原地哈希
程序员吴师兄:无意中发现一位大佬的算法刷题 pdf 笔记 algomooc.com/127.html

版权声明
本文为[程序员吴师兄]所创,转载请带上原文链接,感谢
https://blog.csdn.net/kexuanxiu1163/article/details/114631802

随机推荐