如果一個題目限定了數據范圍是[1, n]內的整數，那么這個題目可以思考的就是

nums[i]和 i 的關系，769. 最多能完成排序的塊?這個題就使用到了子數組中最大值和 連續[0, n - 1]的關系

而對于本題來說，也可以思考[1, n] 和 nums[i] 的關系，想要觀察他們之間的關系

以nums = [1,3,4,2,2]為例，可以畫出如下散點圖，下列散點圖，因為這個題要求不能更改原數組，而且只能使用o(1)的空間復雜度設計算法，所以直接畫出{1, 1},?{2, 3},?{3, 4},?{4, 2}, {5, 2} 這幾個點

這個圖 已經包含了所有nums中的信息，那么如何去解讀這張圖的信息來找到 2這個出現兩次的縱坐標呢？

????????一個很自然的想法就是畫一條水平線，讓這條水平線從上往平移，一旦平移到穿過兩個即以上的點，那么此時這條水平線的縱坐標就是要找的重復兩次的數，這樣的想法就是兩個for循環來實現的o(n2) 的算法，能夠滿足題目要求，但是這樣的算法不能通過全部測試用例

那么怎么解決這個問題？首先想一想有沒有o(nlogn)的解法？

logn的解法中二分就是很常見的算法，可是二分只能針對有序數組進行啊，1 3 4 2 2 算哪門子的有序數組？那不如換個思路，在上圖中畫出四條平行線，y1 = 1, y2 = 2, y3?= 3, y4 = 4,觀察后發現，

y1 穿過以及其下方的點有1個，y2 穿過以及其下方的點有3個，

y3 穿過以及其下方的點有4個，y4 穿過以及其下方的點有5個

正好是在 y2?處多穿過了兩個點，

此時可以根據以上事實發現如下規律：

要找的數是[1,n-1]中的某個target，這個target滿足下列性質

假設x是屬于[1,n-1]中的一個數，記在nums中小于等于x的有yx個

如果yx <= x，則x 一定不是要找到的target，且x < target

如果yx > x，則納入target備選集合中，且x >= target

而target就是備選集合中最小的那個數

那么就可以使用如下算法

class Solution {
public:int findDuplicate(vector<int>& nums) {int n = nums.size();int l = 1, r = n - 1;while(l < r){int mid = l + (r - l) / 2;int count = 0;for(int i = 0; i < n; ++i){if(nums[i] <= mid){count++;}}if(count <= mid){l = mid + 1;}else{r = mid;}}return l;}
};

其實現原理可以通過幾張圖演示

?