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

客官°小女子只卖身不卖艺 2022-11-06 15:00 9阅读 0赞

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

题目链接：[剑指 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-a9617925a1fbad00acf2d41198085c3a_b.jpg]

![v2-b5b7d28c610e7afb05374bd1c5260958\_b.jpg][v2-b5b7d28c610e7afb05374bd1c5260958_b.jpg]

![v2-eab27993c8d397395867db7bfe8fd3de\_b.jpg][v2-eab27993c8d397395867db7bfe8fd3de_b.jpg]

![v2-e7ef18ef40606a0973ee16a842a94f35\_b.jpg][v2-e7ef18ef40606a0973ee16a842a94f35_b.jpg]

![v2-fc9ff7176f11bbf4353ce1f0e33c9061\_b.jpg][v2-fc9ff7176f11bbf4353ce1f0e33c9061_b.jpg]

![v2-00ac030a9e15131c8613c001673cc9ef\_b.jpg][v2-00ac030a9e15131c8613c001673cc9ef_b.jpg]

![v2-1f25bcb7e67a171f759c759f2b9b2534\_b.jpg][v2-1f25bcb7e67a171f759c759f2b9b2534_b.jpg]

![v2-c9d51c5f2d400159fe509a24fb03a92c\_b.jpg][v2-c9d51c5f2d400159fe509a24fb03a92c_b.jpg]

![v2-f5652972b5a6e854bd1782104169a8d6\_b.jpg][v2-f5652972b5a6e854bd1782104169a8d6_b.jpg]

![v2-7d00b9116fb93a9729fae12787d2f0c1\_b.jpg][v2-7d00b9116fb93a9729fae12787d2f0c1_b.jpg]

![v2-70effe556489fd92a1adf4f9ad7f61f5\_b.jpg][v2-70effe556489fd92a1adf4f9ad7f61f5_b.jpg]

![v2-8f62add09931b073b4709b8dec2269ad\_b.jpg][v2-8f62add09931b073b4709b8dec2269ad_b.jpg]

![v2-ba96f0715703269f3dcc0bb6bfeda692\_b.jpg][v2-ba96f0715703269f3dcc0bb6bfeda692_b.jpg]

![v2-d2be4423413e3b902c37e37700b366f7\_b.jpg][v2-d2be4423413e3b902c37e37700b366f7_b.jpg]

![v2-fb7c02a82e47adc6c7b873185d0f00f7\_b.jpg][v2-fb7c02a82e47adc6c7b873185d0f00f7_b.jpg]

![v2-85210bb381b9e4f3354deb4c8523903e\_b.jpg][v2-85210bb381b9e4f3354deb4c8523903e_b.jpg]

![v2-1ec0b3591807f3e9445d5e7cb0becc75\_b.jpg][v2-1ec0b3591807f3e9445d5e7cb0becc75_b.jpg]

![v2-c429da770fca674b31b31743a59d1b65\_b.jpg][v2-c429da770fca674b31b31743a59d1b65_b.jpg]

![v2-c429f8b4633a5ae78cdd6e835476051a\_b.jpg][v2-c429f8b4633a5ae78cdd6e835476051a_b.jpg]

![v2-00ac030a9e15131c8613c001673cc9ef\_b.jpg][v2-00ac030a9e15131c8613c001673cc9ef_b.jpg]

![v2-160f3a955772a8350ee3c170a411e6e7\_b.jpg][v2-160f3a955772a8350ee3c170a411e6e7_b.jpg]

![v2-f09b5ec9d1b0dfea0d8196347cc7ca5b\_b.jpg][v2-f09b5ec9d1b0dfea0d8196347cc7ca5b_b.jpg]

![v2-9bc8c85c40bf37734417cbee6dbb3da1\_b.jpg][v2-9bc8c85c40bf37734417cbee6dbb3da1_b.jpg]

![v2-c74d3a8bbdabc3b4b62f519c2139b249\_b.jpg][v2-c74d3a8bbdabc3b4b62f519c2139b249_b.jpg]

![v2-3245d78229cfb7ca3fcd937dfda50510\_b.jpg][v2-3245d78229cfb7ca3fcd937dfda50510_b.jpg]

![v2-08b89c2a3404cfec73c46713dab70ba4\_b.jpg][v2-08b89c2a3404cfec73c46713dab70ba4_b.jpg]

![v2-eef03d0da22ce606afdb2a7ca47ec7fb\_b.jpg][v2-eef03d0da22ce606afdb2a7ca47ec7fb_b.jpg]

![v2-a0cb41e0b369a7a8fdc2feddd93ccff5\_b.jpg][v2-a0cb41e0b369a7a8fdc2feddd93ccff5_b.jpg]

![v2-bba362868923b28c431803fb6528fc19\_b.jpg][v2-bba362868923b28c431803fb6528fc19_b.jpg]

![v2-3af5458d89ee0e285df72a6275565080\_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 笔记][pdf] [https://www.algomooc.com/127.html][offer _ 03 .]

[offer _ 03 .]: https://link.zhihu.com/?target=https%3A//www.algomooc.com/127.html
[v2-a9617925a1fbad00acf2d41198085c3a_b.jpg]: /images/20221023/b25e29b9692749d38070bf496d3dce25.png
[v2-b5b7d28c610e7afb05374bd1c5260958_b.jpg]: /images/20221023/4c498feee0ec464b9da21327def35e6c.png
[v2-eab27993c8d397395867db7bfe8fd3de_b.jpg]: /images/20221023/1b224e2f368c4fb88f6b426bdc926e57.png
[v2-e7ef18ef40606a0973ee16a842a94f35_b.jpg]: /images/20221023/02e8dec9b5534c618c68396f3d364416.png
[v2-fc9ff7176f11bbf4353ce1f0e33c9061_b.jpg]: /images/20221023/e15f2cd55fe0423f8d26a25d364677af.png
[v2-00ac030a9e15131c8613c001673cc9ef_b.jpg]: /images/20221023/bd943640e9d949fdbaa38be3b5fe56ac.png
[v2-1f25bcb7e67a171f759c759f2b9b2534_b.jpg]: /images/20221023/8967c8f1de3844ec8c1dc83040ab3493.png
[v2-c9d51c5f2d400159fe509a24fb03a92c_b.jpg]: /images/20221023/4c88be3d25b14aafad9f2863a8d3f402.png
[v2-f5652972b5a6e854bd1782104169a8d6_b.jpg]: /images/20221023/d63c9fa7ea734c35afe079c42d3fd32c.png
[v2-7d00b9116fb93a9729fae12787d2f0c1_b.jpg]: /images/20221023/46e35b22a5f04b738d43a04529110395.png
[v2-70effe556489fd92a1adf4f9ad7f61f5_b.jpg]: /images/20221023/7863ba07bc634ecd8107cf4d4c3d0a4c.png
[v2-8f62add09931b073b4709b8dec2269ad_b.jpg]: /images/20221023/10d07de836f94d33acfe029988038fcc.png
[v2-ba96f0715703269f3dcc0bb6bfeda692_b.jpg]: /images/20221023/56eae170faa74554bc44ecdbd52570b3.png
[v2-d2be4423413e3b902c37e37700b366f7_b.jpg]: /images/20221023/339332ce3fe943b5a664826f3393188f.png
[v2-fb7c02a82e47adc6c7b873185d0f00f7_b.jpg]: /images/20221023/04002298f84047df9b98533d5986a74f.png
[v2-85210bb381b9e4f3354deb4c8523903e_b.jpg]: /images/20221023/9b4025a3411946ceaf65b959f1d65741.png
[v2-1ec0b3591807f3e9445d5e7cb0becc75_b.jpg]: /images/20221023/08eb064aaedc478da28e242928ea3a2c.png
[v2-c429da770fca674b31b31743a59d1b65_b.jpg]: /images/20221023/977ed3a5b5a04a6ebdcafea5d48a7d3f.png
[v2-c429f8b4633a5ae78cdd6e835476051a_b.jpg]: /images/20221023/c3a28a4c29b84bdebbd68afe3c9d2342.png
[v2-160f3a955772a8350ee3c170a411e6e7_b.jpg]: /images/20221023/770933665a954228a63b13a8b71515f3.png
[v2-f09b5ec9d1b0dfea0d8196347cc7ca5b_b.jpg]: /images/20221023/8491659f3cd54470800a52020c199bbc.png
[v2-9bc8c85c40bf37734417cbee6dbb3da1_b.jpg]: /images/20221023/6f6332d8526b42d2b422b64ac2e457d9.png
[v2-c74d3a8bbdabc3b4b62f519c2139b249_b.jpg]: /images/20221023/b1792843b25043ac96529d82bb6a7ecd.png
[v2-3245d78229cfb7ca3fcd937dfda50510_b.jpg]: /images/20221023/d0a7c423b5b4411c8c90f13c3a5a40e8.png
[v2-08b89c2a3404cfec73c46713dab70ba4_b.jpg]: /images/20221023/b9a9cd76c6a046e39096227d354146dd.png
[v2-eef03d0da22ce606afdb2a7ca47ec7fb_b.jpg]: /images/20221023/c138dbf590484478bc0054673e09c7c5.png
[v2-a0cb41e0b369a7a8fdc2feddd93ccff5_b.jpg]: /images/20221023/7c536eb0568a4ab990707b4b9deefa16.png
[v2-bba362868923b28c431803fb6528fc19_b.jpg]: /images/20221023/e223933189504fa4b36006b1d919382a.png
[v2-3af5458d89ee0e285df72a6275565080_b.jpg]: /images/20221023/9dcf91a9809e49a48d210d9471688c9a.png
[pdf]: https://zhuanlan.zhihu.com/p/341224925