本篇內(nèi)容介紹了“java怎么在給定的數(shù)組里面尋找重復(fù)數(shù)”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

創(chuàng)新互聯(lián)從2013年開(kāi)始，先為交口等服務(wù)建站，交口等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢(xún)服務(wù)。為交口企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問(wèn)題。

原題

給定一個(gè)包含 n + 1 個(gè)整數(shù)的數(shù)組 nums，其數(shù)字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個(gè)重復(fù)的整數(shù)。假設(shè)只有一個(gè)重復(fù)的整數(shù)，找出這個(gè)重復(fù)的數(shù)。

示例 1:

輸入: [1,3,4,2,2]
輸出: 2

示例 2:

輸入: [3,1,3,4,2]
輸出: 3

說(shuō)明：

• 不能更改原數(shù)組（假設(shè)數(shù)組是只讀的）。

• 只能使用額外的 O(1) 的空間。

• 時(shí)間復(fù)雜度小于 O(n2) 。

• 數(shù)組中只有一個(gè)重復(fù)的數(shù)字，但它可能不止重復(fù)出現(xiàn)一次。

解題

普通思路

針對(duì)說(shuō)明里的前兩條，其實(shí)就分別對(duì)應(yīng)了解題的兩種思路：

1. 先原地排序，再遍歷尋找。

2. 使用集合記錄已經(jīng)出現(xiàn)過(guò)的數(shù)字。

當(dāng)然了，既然已經(jīng)在說(shuō)明里被禁止了， 那么就應(yīng)該想想別的思路了。

我還想到了利用 bitMap 的思路，相當(dāng)于用一個(gè)數(shù)字的二進(jìn)制，各個(gè)位上是否為1來(lái)表示該數(shù)字是否出現(xiàn)過(guò)。但考慮到 java 里 int 的最大值是 (2^31 - 1)，long 的最大值也不過(guò)是(2^63 - 1)，那都是要求 n 不能大于100的。因此，這種思路也是暫時(shí)不可取的。

抽象為環(huán)形鏈表II

如果將數(shù)組的下標(biāo)和值抽象成鏈表的話，出現(xiàn)重復(fù)數(shù)字也就意味著出現(xiàn)鏈表中有環(huán)，那么這道題就是之前做到的力扣142——環(huán)形鏈表II一模一樣了。

我們舉例說(shuō)明一下，假設(shè)數(shù)組是[1, 5, 7, 3, 2, 4, 6, 7]，那么將其轉(zhuǎn)化成的鏈表就是：0 -> 1 -> 5 -> 7 -> 3 -> 2 -> 4 -> 6 -> 7 ....無(wú)限循環(huán)。

那我們就可以借助快慢指針：

1. 快指針一次走兩步，慢指針一次走一步，直到他們相遇；

2. 快指針再次從起點(diǎn)出發(fā)，但此時(shí)兩個(gè)指針都是一次走一步；

3. 當(dāng)他們?cè)俅蜗嘤龊螅嘤鳇c(diǎn)就是重復(fù)的整數(shù)。

接下來(lái)讓我們看看代碼：

class Solution {
   public int findDuplicate(int[] nums) {
       // 參考環(huán)形鏈表II，利用快慢指針
       // 快指針一次走兩步，慢指針一次走一步，當(dāng)他們相遇后
       // 快指針再次從起點(diǎn)出發(fā)，但此時(shí)兩個(gè)指針都是一次走一步
       // 當(dāng)他們?cè)俅蜗嘤龊?，相遇點(diǎn)就是重復(fù)的整數(shù)

       int slow = nums[0];
       int fast = nums[nums[0]];
       while (slow != fast) {
           slow = nums[slow];
           fast = nums[nums[fast]];
       }

       fast = 0;
       while (slow != fast) {
           slow = nums[slow];
           fast = nums[fast];
       }

       return fast;
   }
}

提交OK，時(shí)間復(fù)雜度為：O(n)，空間復(fù)雜度是：O(1)。

“java怎么在給定的數(shù)組里面尋找重復(fù)數(shù)”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！