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

示例 1:

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

代碼

class Solution {public int findDuplicate(int[] nums) {int n=nums.length,l=1,r=n-1;while (l<r){int mid = (l + r+1) >>> 1;int count=0;for(int num:nums)//統計小于mid數字出現的次數{if(num<mid)count++;}if(count>=mid)//如果小于mid數字出現的次數大于mid，則小于mid的數字出現重復r=mid-1;else l=mid;}return l;}
}

解題思路

和環形鏈表一樣，快慢指針，快的每次兩跳，慢的一跳，相遇的時候，慢回起點，快慢都變為每一次一跳，入口就是重復元素

代碼

class Solution {public int findDuplicate(int[] nums) {int s=0,f=0;do {s=nums[s];f=nums[nums[f]];}while (s!=f);s=0;do {s=nums[s];f=nums[f];}while (s!=f);return s;}
}