java怎么在給定的數(shù)組里面尋找重復(fù)數(shù)

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

原題

給定一個(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

說明：

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

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

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

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

解題

普通思路

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

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

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

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

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

抽象為環(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. 快指針再次從起點(diǎn)出發(fā)，但此時(shí)兩個(gè)指針都是一次走一步；

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

接下來讓我們看看代碼：

class Solution {
    public int findDuplicate(int[] nums) {
        // 參考環(huán)形鏈表II，利用快慢指針
        // 快指針一次走兩步，慢指針一次走一步，當(dāng)他們相遇后
        // 快指針再次從起點(diǎn)出發(fā)，但此時(shí)兩個(gè)指針都是一次走一步
        // 當(dāng)他們再次相遇后，相遇點(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)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！