力扣思维题——寻找重复数

题目链接：https://leetcode.cn/problems/find-the-duplicate-number/description/?envType=study-plan-v2&envId=top-100-liked

这题的思维难度较大。一种是利用双指针法进行计算环的起点，这种方法在面试里很难说清楚，也很难想到。大致做法就是，定义快慢指针，由于数字都是1-n，一共n+1个所以一定存在环。快慢指针一定会相遇，但是相遇的点并不是重复数字的点，所以再将fast放到起点，每次移动一格，再次和慢指针相遇的时候就是环的起点，两个指针每次都是一样快了。

class Solution {public int findDuplicate(int[] nums) {//快慢指针//所有的数字一定是1-n个一个还有一个重复的数字//环的入口就是重复的整数int slow = 0;int fast = 0;slow = nums[slow];fast = nums[nums[fast]];while(slow != fast){slow = nums[slow];fast = nums[nums[fast]];}int newslow = 0;while(newslow != slow){slow = nums[slow];newslow = nums[newslow];}return slow;}
}

另：二分查找法。推荐面试时候写这种，一来和面试官好解释，二来里面涉及常规算法能扯皮。

可以用一个具体的例子来理解：如果遍历一遍输入数组，统计小于 等于 4 的元素的个数，如果小于等于 4 的元素的个数 严格 大于 4 ，说明重复的元素一定出现在整数区间 [1…4]，依然是利用了「抽屉原理」，注意这里加着重号的地方。

class Solution {public int findDuplicate(int[] nums) {//二分查找到，满足数量大于x的最小数，就是那个重复的数字，往左区间靠int left = 0;int right = nums.length-1;while(left<right){int mid = (left+right)/2;int count = 0;for(int i=0;i<nums.length;i++){if(nums[i]<=mid){count++; }}if(count>mid)right = mid;//mid==count说明，mid包括mid前面一定不存在重复的数字else left = mid+1;}return left;}
}