今天分享的題目來源于 LeetCode 上的劍指 Offer 系列 面試題03. 數(shù)組中重復(fù)的數(shù)字。

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

一、題目描述

找出數(shù)組中重復(fù)的數(shù)字。

在一個長度為 n 的數(shù)組 nums 里的所有數(shù)字都在 0～n-1 的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個數(shù)字重復(fù)了，也不知道每個數(shù)字重復(fù)了幾次。請找出數(shù)組中任意一個重復(fù)的數(shù)字。

示例 1：

輸入： [2,?3,?1,?0,?2,?5,?3] 輸出：2?或?3?

限制：

2?<=?n?<=?100000

二、題目解析

注意題目描述：一個長度為 n 的數(shù)組 nums 里的所有數(shù)字都在 0～n-1 的 范圍內(nèi)，這個 范圍 恰好與數(shù)組的下標(biāo)可以一一對應(yīng)。

所以我們可以執(zhí)行某種操作，使索引與值一一對應(yīng)，即索引 0 的值為 0，索引 1 的值為 1。而一旦某個索引的值不只一個，則找到了重復(fù)的數(shù)字，也即發(fā)生了 哈希沖突。

三、動畫描述

四、圖片描述

五、參考代碼

class?Solution?{public?int?findRepeatNumber(int[]?nums)?{//設(shè)索引初始值為?i?=?0int?i?=?0;//遍歷整個數(shù)組?nums?while(i?<?nums.length)?{//索引?i?的值為?i,無需執(zhí)行交換操作，查看下一位if(nums[i]?==?i)?{i++;continue;}//索引?nums[i]?處的值也為?nums[i]，即找到一組相同值，返回?nums[i]?即可if(nums[nums[i]]?==?nums[i])?return?nums[i];//執(zhí)行交換操作，目的是為了使索引與值一一對應(yīng)，即索引?0?的值為?0，索引?1?的值為?1int?tmp?=?nums[i];nums[i]?=?nums[tmp];nums[tmp]?=?tmp;}//如果遍歷整個數(shù)組都沒有找到相同的值，返回?-1return?-1;} }

六、復(fù)雜度分析

時間復(fù)雜度

遍歷數(shù)組需要 O(N) 時間。

注意參考代碼里面的關(guān)鍵字 continue，這表示在 while 的一次循環(huán)里面，只有這次循環(huán)將 索引(i) 與 索引值(num[i]) 匹配到了，才會執(zhí)行下一次循環(huán)。

在每一次的循環(huán)過程中，索引(i) 與 索引值(num[i]) 匹配到后，在后續(xù)的循環(huán)過程中不會操作它們，所以雖然一開始的循環(huán)過程中，執(zhí)行的交換操作較多，但在后續(xù)的循環(huán)過程中根本不需要再執(zhí)行操作了。

根據(jù)均攤復(fù)雜度分析 ，總的時間復(fù)雜度為 ?O(N) ，N 為數(shù)組的長度。

空間復(fù)雜度

使用常數(shù)復(fù)雜度的額外空間，為 ?O(1)。

往期推薦

多圖證明，Java到底是值傳遞還是引用傳遞？

2020-09-02

面試系列第2篇：回文字符串判斷的3種方法！

2020-08-24

面試系列第1篇：常見面試題和面試套路有哪些？

2020-08-21

關(guān)注下方二維碼，收獲更多干貨！

總結(jié)

以上是生活随笔為你收集整理的图解面试题：找出数组中重复的数字？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。