java怎么在給定的數組里面尋找重復數

本篇內容介紹了“java怎么在給定的數組里面尋找重復數”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

原題

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

示例 1:

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

示例 2:

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

說明：

• 不能更改原數組（假設數組是只讀的）。

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

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

• 數組中只有一個重復的數字，但它可能不止重復出現一次。

解題

普通思路

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

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

2. 使用集合記錄已經出現過的數字。

當然了，既然已經在說明里被禁止了， 那么就應該想想別的思路了。

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

抽象為環形鏈表II

如果將數組的下標和值抽象成鏈表的話，出現重復數字也就意味著出現鏈表中有環，那么這道題就是之前做到的力扣142——環形鏈表II一模一樣了。

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

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

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

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

3. 當他們再次相遇后，相遇點就是重復的整數。

接下來讓我們看看代碼：

class Solution {
    public int findDuplicate(int[] nums) {
        // 參考環形鏈表II，利用快慢指針
        // 快指針一次走兩步，慢指針一次走一步，當他們相遇后
        // 快指針再次從起點出發，但此時兩個指針都是一次走一步
        // 當他們再次相遇后，相遇點就是重復的整數

        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，時間復雜度為：O(n)，空間復雜度是：O(1)。

“java怎么在給定的數組里面尋找重復數”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！