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

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

原題

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

示例 1:

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

示例 2:

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

說明：

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

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

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

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

解題

普通思路

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

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

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

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

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

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

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

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

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

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

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

3. 當(dāng)他們再次相遇后，相遇點就是重復(fù)的整數(shù)。

接下來讓我們看看代碼：

class Solution {
   public int findDuplicate(int[] nums) {
       // 參考環(huán)形鏈表II，利用快慢指針
       // 快指針一次走兩步，慢指針一次走一步，當(dāng)他們相遇后
       // 快指針再次從起點出發(fā)，但此時兩個指針都是一次走一步
       // 當(dāng)他們再次相遇后，相遇點就是重復(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，時間復(fù)雜度為：O(n)，空間復(fù)雜度是：O(1)。

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

本文標(biāo)題：java怎么在給定的數(shù)組里面尋找重復(fù)數(shù)
分享URL：http://chinadenli.net/article22/pijdjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供做網(wǎng)站、網(wǎng)站制作、網(wǎng)站策劃、營銷型網(wǎng)站建設(shè)、品牌網(wǎng)站建設(shè)、網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)