題目

標題和出處

標題：尋找重復數

出處：287. 尋找重復數

難度

6 級

題目描述

要求

給定一個包含 $\text{n}+\text{1}$ 個整數的數組 $\text{nums}$，每個整數都在范圍 $\text{[1,?n]}$ 內（包括 $\text{1}$ 和 $\text{n}$）。

數組 $\text{nums}$ 只有一個重復的整數，返回這個重復的數。

要求不修改數組 $\text{nums}$ 且只用常量級的額外空間。

示例

示例 1：

輸入：$\text{nums?=?[1,3,4,2,2]}$
輸出：$\text{2}$

示例 2：

輸入：$\text{nums?=?[3,1,3,4,2]}$
輸出：$\text{3}$

示例 3：

輸入：$\text{nums?=?[3,3,3,3,3]}$
輸出：$\text{3}$

數據范圍

• $\text{1}\le \text{n}\le {\text{10}}^{\text{5}}$
• $\text{nums.length}=\text{n}+\text{1}$
• $\text{1}\le \text{nums[i]}\le \text{n}$
• $\text{nums}$ 中的所有整數都只出現一次，除了一個整數出現兩次或多次

進階

• 如何證明 $\text{nums}$ 中至少存在一個重復的數字？
• 你可以設計一個線性級時間復雜度的解決方案嗎？

前言

由于數組的長度是 $n+1$，且最多包含 $n$ 個不同的整數。根據抽屜原理（或鴿籠原理）可知，將數組的 $n+1$ 個位置分配到 $n$ 個不同的整數，至少有兩個位置分配到同一個整數，即該整數在數組中重復。因此數組中至少存在一個重復的數字。

由于這道題要求不修改數組且空間復雜度是 $O(1)$，因此排序、哈希表等解法都是不允許的，需要使用其他解法尋找重復的數字。

解法一

思路和算法

每個正整數的二進制表示中至少有一位是 $1$。對于二進制表示的每一位，分別考慮數組 $\text{nums}$ 中的所有整數在該位的 $1$ 的次數 $\text{countArr}$ 和范圍 $[1,n]$ 中的所有整數在該位的 $1$ 的次數 $\text{countNum}$。假設整數 $x$ 在數組 $\text{nums}$ 中出現超過一次，則 $x$ 的二進制表示的每個 $1$ 所在的位都滿足 $\text{countArr}>\text{countNum}$。理由如下。

• 如果 $x$ 出現兩次，則范圍 $[1,n]$ 中的所有整數都在數組 $\text{nums}$ 中出現，因此對于 $x$ 中等于 $1$ 的每一位都有 $\text{countArr}>\text{countNum}$。

• 如果 $x$ 出現超過兩次，則范圍 $[1,n]$ 中的部分整數不在數組 $\text{nums}$ 中出現，可以看成 $x$ 替代了這部分整數。對于 $x$ 中等于 $1$ 的每一位，被替代的整數在相應位的值等于 $0$ 或 $1$。替代之前有 $\text{countArr}>\text{countNum}$，替代之后同樣有 $\text{countArr}>\text{countNum}$。

除了 $x$ 的二進制表示的每個 $1$ 所在的位以外，其余位都不滿足 $\text{countArr}>\text{countNum}$。因此上述結論的逆命題也成立：假設所有滿足 $\text{countArr}>\text{countNum}$ 的位組成的整數是 $x$，則 $x$ 在數組 $\text{nums}$ 中出現超過一次。

根據上述分析，可以使用位運算尋找重復數。首先找到 $n$ 的二進制表示的最高有效位，即最高位 $1$ 所在的位數，然后依次遍歷最低有效位到最高有效位，對于每一位計算 $\text{countArr}$ 和 $\text{countNum}$，如果 $\text{countArr}>\text{countNum}$ 則將該位加到重復數中。遍歷結束之后即可得到重復數。

代碼

class Solution {public int findDuplicate(int[] nums) {int n = nums.length - 1;int highBit = 0;int temp = n;while (temp != 0) {highBit = temp & (-temp);temp -= highBit;}int duplicate = 0;for (int i = 1; i <= highBit; i <<= 1) {int countArr = 0, countNum = 0;for (int num : nums) {int bit = num & i;if (bit != 0) {countArr++;}}for (int j = 1; j <= n; j++) {int bit = j & i;if (bit != 0) {countNum++;}}if (countArr > countNum) {duplicate += i;}}return duplicate;}
}

復雜度分析

• 時間復雜度：$O(n\log n)$，其中 $n$ 是數組 $\text{nums}$ 的長度減 $1$。需要遍歷的二進制表示位數是 $O(\log n)$，對于每一位都需要 $O(n)$ 的時間計算該位在重復數中是否等于 $1$，時間復雜度是 $O(n\log n)$。

• 空間復雜度：$O(1)$。

解法二

思路和算法

假設有一個長度為 $n+1$ 的數組 $\text{counts}$，其中 $\text{counts}[i]$ 表示數組 $\text{nums}$ 中的不超過 $i$ 的整數個數。以下用 $x$ 表示重復數。

如果 $x$ 出現兩次，則當 $i<x$ 時 $\text{counts}[i]=i$，當 $i\ge x$ 時 $\text{counts}[i]=i+1>i$。

如果 $x$ 出現超過兩次，則范圍 $[1,n]$ 中的部分整數不在數組 $\text{nums}$ 中出現，可以看成 $x$ 替代了這部分整數，假設只有一個整數被替代，用 $j$ 表示被替代的整數，分別考慮 $j<x$ 和 $j>x$ 的情況。

• 如果 $j<x$，則對于 $i<x$，不超過 $i$ 的整數個數不變或減少，因此 $\text{counts}[i]\le i$，對于 $i\ge x$，不超過 $i$ 的整數個數不變，因此 $\text{counts}[i]>i$。

• 如果 $j>x$，則對于 $i<x$，不超過 $i$ 的整數個數不變，因此 $\text{counts}[i]=i$，對于 $i\ge x$，不超過 $i$ 的整數個數不變或增加，因此 $\text{counts}[i]>i$。

因此當 $i<x$ 時 $\text{counts}[i]\le i$，當 $i\ge x$ 時 $\text{counts}[i]>i$。如果被替代的整數有多個，該結論仍成立。

重復數 $x$ 是使得 $\text{counts}[x]>x$ 成立的最小整數 $x$，可以使用二分查找的方法尋找重復數。

用 $\text{low}$ 和 $\text{high}$ 分別表示二分查找的下界和上界。由于 $x$ 在范圍 $[1,n]$ 中，因此初始時 $\text{low}=1$，$\text{high}=n$。

每次查找時，取 $\text{mid}$ 為 $\text{low}$ 和 $\text{high}$ 的平均數向下取整，計算數組 $\text{nums}$ 中的不超過 $\text{mid}$ 的整數個數 $\text{counts}[\text{mid}]$，執行如下操作。

• 如果 $\text{counts}[\text{mid}]\le \text{mid}$，則重復數 $x$ 小于等于 $\text{mid}$，因此在 $[\text{low},\text{mid}]$ 中繼續查找。

• 如果 $\text{counts}[\text{mid}]>\text{mid}$，則重復數 $x$ 大于 $\text{mid}$，因此在 $[\text{mid}+1,\text{high}]$ 中繼續查找。

當 $\text{low}=\text{high}$ 時，查找結束，此時 $\text{low}$ 即為重復數 $x$。

實現方面，并不需要顯性創建數組 $\text{counts}$，而是可以在二分查找的過程中根據當前的 $\text{mid}$ 遍歷數組 $\text{nums}$ 計算不超過 $\text{mid}$ 的整數個數，因此空間復雜度是 $O(1)$。

代碼

class Solution {public int findDuplicate(int[] nums) {int n = nums.length - 1;int low = 1, high = n;while (low < high) {int mid = low + (high - low) / 2;int count = 0;for (int num : nums) {if (num <= mid) {count++;}}if (count > mid) {high = mid;} else {low = mid + 1;}}return low;}
}

復雜度分析

• 時間復雜度：$O(n\log n)$，其中 $n$ 是數組 $\text{nums}$ 的長度減 $1$。需要執行 $O(\log n)$ 次二分查找，每次二分查找需要 $O(n)$ 的時間遍歷數組 $\text{nums}$ 計算不超過特定值的整數個數，時間復雜度是 $O(n\log n)$。

• 空間復雜度：$O(1)$。

解法三

思路和算法

將數組看成有向圖，范圍 $[0,n]$ 中的每個整數是一個結點，對于 $0\le i\le n$ 的每個下標 $i$，存在一條從 $i$ 指向 $\text{nums}[i]$ 的有向邊。對于重復數 $x$，存在至少兩條指向 $x$ 的邊，因此有向圖中存在環。

這道題可以看成在有向圖中尋找環的入口，可以使用「環形鏈表 II」的快慢指針做法。以下只說明使用快慢指針尋找重復數的做法，正確性證明見「環形鏈表 II 的題解」。

尋找重復數分成兩步。

第一步是使用快慢指針遍歷有向圖尋找相遇點。

初始時，快指針和慢指針都位于整數 $0$。每次將快指針移動兩步，慢指針移動一步，在至少移動一次的情況下，當快指針和慢指針相遇時，相遇的位置為相遇點。

第二步是將兩個指針分別從起點和相遇點開始遍歷有向圖尋找重復數。

初始時，兩個指針分別位于整數 $0$ 和相遇點。每次將兩個指針各移動一步，兩個指針相遇的整數即為重復數。

代碼

class Solution {public int findDuplicate(int[] nums) {int fast = 0, slow = 0;int meet = -1;while (meet < 0) {fast = nums[nums[fast]];slow = nums[slow];if (fast == slow) {meet = fast;}}int pointer1 = 0, pointer2 = meet;while (pointer1 != pointer2) {pointer1 = nums[pointer1];pointer2 = nums[pointer2];}return pointer1;}
}

復雜度分析

• 時間復雜度：$O(n)$，其中 $n$ 是數組 $\text{nums}$ 的長度減 $1$。快慢指針的時間復雜度是 $O(n)$。

• 空間復雜度：$O(1)$。