力扣 寻找重复数

二分，双指针，环形链表。

题目

不看完题就是排序后，用两个快慢指针移动，找到相同就返回即可。

class Solution {public int findDuplicate(int[] nums) {Arrays.sort(nums);int l=0;int r=1;while(r<nums.length){if(nums[l]==nums[r])return nums[r];l++; r++;}return -1;}
}

但是题要求不修改数组，因此肯定不会那么简单。先是二分查找法，由题可知，nums只有一个重复的数，且数字的大小在1到n，那么可以直接看nums[i]，去遍历每个数值，然后用一个计数器去记录i，注意假设nums[x]找到了这个数，那后面的计数器nums[x+1]都是加一的，然后二分划分区间，没有重复的在左半区，重复数后的在右半区，重复数就是要找的mid。如果比目标值即重复的数小说明没有，跟目标值相等说明刚好一个，说明当前没有找到重复的数，比目标值大说明就是找到了重复数的区间，继续收缩。然后就是二分的模板了，注意比较时是比数值不是比索引。

时间复杂度： O(nlogn)，空间复杂度： O(1)。

class Solution {public int findDuplicate(int[] nums) {int n = nums.length;int l = 1, r = n - 1, ans = -1;while (l <= r) {int mid = (l + r) >> 1;int cnt = 0;for (int i = 0; i < n; ++i) {if (nums[i] <= mid) {cnt++;}}if (cnt <= mid) {l = mid + 1;} else {r = mid - 1;ans = mid;}}return ans;}
}

接着是快慢指针，龟兔赛跑算法。这题由于索引跟元素值的限定范围，假如按索引指向的数值当作下一个索引，如此往复，是可以形成一个环的，即假设走到某个k+1点时指向的数值是k，然后去到索引k，索引k的数值是k+2，然后k+2的数值又是k，如此反复，这里是可以形成一个环的，而这个k+1时就是环的入口点，也是要找的重复值。然后用快慢指针，慢指针每次走一步，快指针每次走两步，相遇一次后做标记，慢指针归零，从新出发，快指针从环里出发，然后再次相遇即可找到入口点了。慢指针走一步 slow = slow.next，快指针走两步 fast = fast.next.next，换成数组就是包多一层即可。注意要排除形成自环，即索引的数值是本身，因此从零出发可以排除。

时间复杂度： O(n)，空间复杂度： O(1)。

class Solution {public int findDuplicate(int[] nums) {int slow = 0, fast = 0;//初始化是相等的，所以先执行，第一次相遇找到标记点do {slow = nums[slow];fast = nums[nums[fast]];} while (slow != fast);//慢指针重新出发，快指针继续在环里走slow = 0;while (slow != fast) {slow = nums[slow];fast = nums[fast];}return slow;}
}