图解面试题：找出数组中重复的数字？

忘是亡心i 2023-10-05 09:33 39阅读 0赞

![format_png][]

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

题目链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

#### 一、题目描述 ####

找出数组中重复的数字。

在一个长度为 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。而一旦某个索引的值不只一个，则找到了重复的数字，也即发生了 **哈希冲突**。

#### 三、动画描述 ####

#### 四、图片描述 ####

![format_png 1][]

![format_png 2][]

![format_png 3][]

![format_png 4][]

![format_png 5][]

![format_png 6][]

![format_png 7][]

![format_png 8][]

![format_png 9][]

![format_png 10][]

![format_png 11][]

![format_png 12][]

![format_png 13][]

![format_png 14][]

![format_png 15][]

![format_png 16][]

![format_png 17][]

![format_png 18][]

![format_png 19][]

![format_png 20][]

![format_png 21][]

![format_png 22][]

![format_png 23][]

![format_png 24][]

![format_png 25][]

![format_png 26][]

![format_png 27][]

![format_png 28][]

![format_png 29][]

![format_png 30][]

#### 五、参考代码    ####

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)**。

![format_png 31][]

往期推荐

[多图证明，Java到底是值传递还是引用传递？][Java]

[2020-09-02][Java]

[![format_png 32][] ][Java]

[面试系列第2篇：回文字符串判断的3种方法！][2_3]

[2020-08-24][2_3]

[![format_png 33][] ][2_3]

[面试系列第1篇：常见面试题和面试套路有哪些？][1]

[2020-08-21][1]

[![format_png 34][] ][1]

关注下方二维码，收获更多干货！

![format_png 35][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0MnV5NkdzZGYyNUNtcmFpYTdpY0RJRmtUWEtMSWVRVktwWVlnbTZsOEdDMDQ0aEw4OFg5alNMT0EvNjQw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0ZERFOFZlU2ljUUdpYklWaHdaZFZBNEZ5djdTeFE3YTc4cDBhQ1Y4ajloRGljS1RpYkxFWXZ1T01KUS82NDA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0bjdETEFXOU5ITFU2WmszVk0zb0dIZVR4RTE4MnNhVEhEZGlhRm56UXc2MzJKYlp0N0pTc1pEZy82NDA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0VlBKZmliY3ZjOFlyTnU3WkZWSlpvd01Cemxmd2ljY2dxczJRYnk0NXpuRG9VOUtVckFrM1hMRGcvNjQw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0UDhpYlA0UmQ4c2htcjNjVzZKaEtlc0R5ZW96aWNLcVZqWDZSS0lvdmEwUWtxbkhpYlJ5N1dOVVpnLzY0MA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0cUlHaWMzU2xOU2NNVGljd1dGNjcyb0JKN2liYjNFd1hITFpBOXJvT3hyeGpwaWFpYlNhY2ZmeHpSMGcvNjQw?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0STlBbXRjSzZ2VkY1djJhNVlKeDVlME9ZVUZmZHgxbnJvaWNNUTN5ZEp2aGEyckRQamVKVWFYUS82NDA?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0WnE1VzN6dFh6eXNiSEZyWFU3NnpiWUdiU0k5OEtXenF6bGljMHNHR0ZSZldWNGo4aWNBYVFpY3FnLzY0MA?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0QjE0RlRzZzFNcGljaWFuVlFHTzhuV012bzdQdUJRSVhVYjk4NHJoYXBlamxyR1Fvb250aWNBaWJwZy82NDA?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0Qm56dGliNGRMYzJrS3ZCWWljbGdDWGJNd1F6a2czTzV2cnRUQ1k5aWJSZ1F6cHhKT1V4dGlhYVVNUS82NDA?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0WDdRMzF2Zm5LMXRhbll3SE9mZVd5RUdFV2RBMzA4UW5wV1JGWGliVmNVbDA1aWFJWjlFbFl2SEEvNjQw?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0Z1ljdGtVMkpQOTNrNzJLTmNzYzVkMzdUME1oUklFb0E3cGlja0RUNmxMOXdyMGd3YTVkaWFoUUEvNjQw?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0SUJzd25QY0phcnRrRzZwbXBaZWtPUVBLdzFpYW1YUVhpY1FqaWJ2TVJtejV5Y1FBSkFYaWJhSDg0US82NDA?x-oss-process=image/format,png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0dmxnT2JkZUhVQTNFREI0a3lpY25IQVZVaWFMRG13cnlnYW5YazhpYk82Q0pPZ2drcFlpYXpnN05BQS82NDA?x-oss-process=image/format,png
[format_png 14]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0dHBDNE5hS0MxOU4yeGpvWGNBMXRrVFJpYWNXbHk0a0Q1NDcwU3lIdDRSaWFnUURVaHhYQXhPQ1EvNjQw?x-oss-process=image/format,png
[format_png 15]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0RVdWZ3RaWU9yWGJKemUzQWR4YmlhMktEZ0kybHZYMG9YRGxQRW5pYmhWODByV3VEblk4a0Y1YUEvNjQw?x-oss-process=image/format,png
[format_png 16]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0czBMdVJFMHd6bEJpYlNxWWZpY2RlWGcyVVpHeWJRcDFVeUEyTGliT0xSMzBNMXFMb1RRRWZMMWliUS82NDA?x-oss-process=image/format,png
[format_png 17]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0N0ZnSzhLRHlHSGNLSVNibERuaWJ0ZnViWVFCMU1pYm82VUFIdDhTNDVBOGY0c1RDZlZocnl2dGcvNjQw?x-oss-process=image/format,png
[format_png 18]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0NG1oaEE1Q1pSajdKZE9PU1ljaktkRmZzQkhibmx0ajdjbWdtVWhrNEVKcjBrWmEyRGFCZW13LzY0MA?x-oss-process=image/format,png
[format_png 19]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0S1VXN2tpYkdxdE1rMldEZFBTazU4UDRpYTNYMG9PSkhYNXhyRWdiaE1Ea0ZpY08xZFRQN2xhaHJnLzY0MA?x-oss-process=image/format,png
[format_png 20]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0VU9UQ3pzNWNKSUNGcERsQlNpY2tDZ0M4dzJpYVZnb1I1c3hJSnMwbkZEdE13RTZMTGlhZ3E4TXBnLzY0MA?x-oss-process=image/format,png
[format_png 21]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0U2libFhySkI1dVozdnF0OVhrYnhRWk9ha3FTSDBSSjJoNE9qalpUUnlSejVHc2VpYzh3VXBpYmljZy82NDA?x-oss-process=image/format,png
[format_png 22]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0S2F6Z2pXcnNnaWNpY2FzUzNGYldFNGlhYk1sR1RCR25qdENDWERpYWppY2xSQU9pYWZ0SlE0eE1zYm53LzY0MA?x-oss-process=image/format,png
[format_png 23]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0czA2eGJ6aFFCNTZzcjVmWW9pYmljclp4UFNEaGhUaWNLc3FUSzdSZU91cWIzMWRSa0pjazhzY3FnLzY0MA?x-oss-process=image/format,png
[format_png 24]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0aWJQck9tMEwyS09OWWM4blFpYlpMcUpRNzJMeWt2aEs3RENaVWdGcHNIaEhleGV0VXp3a2M4YWcvNjQw?x-oss-process=image/format,png
[format_png 25]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0eWxLZHJpYmJuVFVHd2ozTkwwUzhOaWJqb1NUZUZMYUZ6RDhhYmNveDRJMU9GdWljRTdiNVVucXF3LzY0MA?x-oss-process=image/format,png
[format_png 26]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0WERqMFhmTmQ3YnhpYlJXb1JWTVN5UzJqUDZNaWJUaHZhV09FaWFDQzJvaWFjSTNJakdGMklGTEk5QS82NDA?x-oss-process=image/format,png
[format_png 27]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0SlM0MUR2Qkl3bVAxWjJLaWMzMGg1cFVJbFhTY0dZT0VEOTdDbzd3T2hkZms1MVMzWXhVM3dIUS82NDA?x-oss-process=image/format,png
[format_png 28]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0ZjQxdjhFSkowaWFsMHhxZ3RpYW90T29laWNuQmYxVmhTY1BJVFFqVzNUdTlXM1poT2pTOFFYeXpRLzY0MA?x-oss-process=image/format,png
[format_png 29]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0dGljRGF6RG1hTDloOWliTVN0OE85dEsyVzRqeVFUS0hWYTBGWXlRTU5YY2ZyemJIRWt5ckhLdncvNjQw?x-oss-process=image/format,png
[format_png 30]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVRpY3NMejJjRHBFUjRLd1BzZHBPbjB0MmI0ZWJnSXMxcjV1dGV5bW5aSXJjSGtQaWFXUVBhQjE4WWFiZW4yTm9Lc28wMGlhenIzVmxpYVdBLzY0MA?x-oss-process=image/format,png
[format_png 31]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9iOTZDaWJDdDcwaWFid2p5b2pMaEEwM1B0eFVua05QUkVudDJGNDh5d2ZYTHBEZERBamljT1RQSThROTR0VkxiSjU4dGJSczEyaWFYREtoVU9XOWdkNE5sRkEvNjQw?x-oss-process=image/format,png
[Java]: http://mp.weixin.qq.com/s?__biz=MzU1NTkwODE4Mw%3D%3D&chksm=fbcc7ea7ccbbf7b14e3af50eee3707d5edb3d5f5aaea542faa923a289a0f2475e73b0a0381a1&idx=1&mid=2247488415&scene=21&sn=b6e8512787df3b8ce5ebdb18883f19a6#wechat_redirect
[format_png 32]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Icld3Nlp1WENzaFlxaWE3dFdiTEU2N2liQ0pZcVFpY3pZSTl5UDEyY2x4Y2VaamxQZGNBaWFnSXNjQzFzd3VlT2xlVExDcW43c0NrN1JJdkdSekhReGpYQUEvNjQw?x-oss-process=image/format,png
[2_3]: http://mp.weixin.qq.com/s?__biz=MzU1NTkwODE4Mw%3D%3D&chksm=fbcc7fc5ccbbf6d31a703c61257373822a777d0c8e74858c506759c647f7431e8e8a63988970&idx=1&mid=2247488253&scene=21&sn=15b0d4ce691c89845df1a829382e81c7#wechat_redirect
[format_png 33]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Icld3Nlp1WENzaDEwamlhRGliNzlyZGliem1mMnY1dUhpYXpuV1JzMERMcHJ0UkYxTGdocjZBaWNIQVI5b3FmYVBaWXdqdkc1M25vcjRubG9pYVF6RWljTGljd0RRLzY0MA?x-oss-process=image/format,png
[1]: http://mp.weixin.qq.com/s?__biz=MzU1NTkwODE4Mw%3D%3D&chksm=fbcc7fd8ccbbf6ce46927c073fb69f9db5eb813435a8cb14a17a37c52765c7dd2bc09a374e26&idx=1&mid=2247488224&scene=21&sn=e24bb38daff651aad5170ae2cad08de3#wechat_redirect
[format_png 34]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Icld3Nlp1WENzaWEwNEVTdGRudjhtbkN3YjUxYVZqd21BMmRXajZBQzRpYkJRSmNQd3dzMllZcGxjbVloR0VUUlZ1OTVjZmdKQ3U3YWdBR0M4ZWlibUVpYWcvNjQw?x-oss-process=image/format,png
[format_png 35]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9zWnlBSnRpYWVzV2NqajRZNmIyUnNZampPNGNtc0E3OXZKY2RyY080RDZxb2t6V1l6NjQ4S2ZQVFNsSWhCeWVKbGZzQmtLaWFzWHR4a2JSTFRUSUxRcGlidy82NDA?x-oss-process=image/format,png