【前言】本文以及之后的一些題解都會(huì)陸續(xù)整理到目錄中，若想了解全部題解整理，請看這里：

第0006頁 · 尋找重復(fù)數(shù)

? ? ? ? 今天想討論的一道題在 LeetCode 上評論也是頗為“不錯(cuò)”。有一說一，是道好題，不過我們還是得先理解了它才算真正的好題。這里我們展示一種使用二進(jìn)制的做法，希望能幫到你喲！

【尋找重復(fù)數(shù)】給定一個(gè)包含?n + 1?個(gè)整數(shù)的數(shù)組?nums?，其數(shù)字都在?[1, n]?范圍內(nèi)（包括?1?和?n），可知至少存在一個(gè)重復(fù)的整數(shù)?，F(xiàn)在假設(shè)?nums?只有一個(gè)重復(fù)的整數(shù)，請返回這個(gè)重復(fù)的數(shù)。要求：你設(shè)計(jì)的解決方案必須不修改數(shù)組?nums?且只用常量級?O(1)的額外空間。

示例1	示例2	示例3
輸入：nums = [1, 3, 4, 2, 2]	輸入：nums = [3, 1, 3, 4, 2]	輸入：nums = [3, 3, 3, 3, 3]
輸出：2	輸出：3	輸出：3

【解題分析】這道題目最難的地方莫過于它的要求：只能使用常量級的額外空間！既然不能用一般的方法，我們便另辟蹊徑，對所有數(shù) [1, n] 進(jìn)行二進(jìn)制展開，舉個(gè)例子如下表所示：

	1	3	4	2	2	x	y
第 0 位	1	1	0	0	0	2	2
第 1 位	0	1	0	1	1	3	2
第 2 位	0	0	1	0	0	1	1

? ? ? ? 對于第 i 位，我們用 x 記錄 nums 中所有數(shù)滿足二進(jìn)制形式下第 i 位是 1 的數(shù)量有多少。用 y 記錄 1 ~ n 中所有數(shù)在二進(jìn)制形式下第 i 位是 1 的數(shù)量應(yīng)該有多少。

? ? ? ? 比如說，上表中第 0 位，nums 中的數(shù)有 2 個(gè)的二進(jìn)制形式該位為 1，而 1 ~ 4 中該位為 1 的數(shù)有 2 個(gè)。?

? ? ? ? 那么怎么找出重復(fù)的數(shù)呢？假設(shè)重復(fù)的數(shù)是 k，那么，對于 k 二進(jìn)制展開后所有為 1 的數(shù)位必定會(huì)導(dǎo)致 x > y。

????????但是這個(gè)結(jié)論我們還是需要證明一下的。

【證明】

????????如果 nums 數(shù)組中 target 出現(xiàn)了 2 次，其余的數(shù)各出現(xiàn)了 1 次，那么如果?target 的第 i 位為 1，那么 nums 數(shù)組的第 i 位 1 的個(gè)數(shù) x 恰好比 y 大了 1。如果 target 的第 i 位為 0，那么 x = y。

? ? ? ? 如果 nums 數(shù)組中 target 出現(xiàn)了 3 次及以上，那么必然有一些數(shù)不在 nums 數(shù)組中。這個(gè)時(shí)候就相當(dāng)于我們用 target 替換了這些數(shù)，我們要考慮的就是這樣的替換對 x 會(huì)產(chǎn)生什么影響：? ? ? ?

? ? ? ? 1、如果被替換的數(shù)第 i 位為 1，且 target 第 i 位為 1：x 不變，滿足 x>y。
? ? ? ? 2、如果被替換的數(shù)第 i 位為 0，且 target 第 i 位為 1：x 加一，滿足 x>y。
? ? ? ? 3、如果被替換的數(shù)第 i 位為 1，且 target 第 i 位為 0：x 減一，滿足 x≤y。
? ? ? ? 4、如果被替換的數(shù)第 i 位為 0，且 target 第 i 位為 0：x 不變，滿足 x≤y。

? ? ? ? 總而言之，在替換后，如果 target 的第 i 位為 1，那么始終滿足 x > y；如果為 0，那么每次替換后始終滿足 x?≤ y。因此，接下來我們只需要按照位次復(fù)原這個(gè)數(shù)就可以了。

?

【源碼展示】

class Solution {
public:int findDuplicate(vector<int>& nums) {int n = nums.size(), ans = 0;// 確定二進(jìn)制下最高位是多少int bit_max = 31;while (!((n - 1) >> bit_max)) {bit_max -= 1;}for (int bit = 0; bit <= bit_max; bit++) {int x = 0, y = 0;for (int i = 0; i < n; ++i) {if (nums[i] & (1 << bit)) {x += 1;}if (i >= 1 && (i & (1 << bit))) {y += 1;}}if (x > y) {ans |= 1 << bit;}}return ans;}
};