门户网站编辑联系方式,上海建设工程招投标网,城乡建设证书查询官网,网站推广渠道的类型题目链接#xff1a;https://leetcode.cn/problems/find-the-duplicate-number/description/?envTypestudy-plan-v2envIdtop-100-liked
这题的思维难度较大。一种是利用双指针法进行计算环的起点#xff0c;这种方法在面试里很难说清楚#xff0c;也很难想到。大致做…题目链接https://leetcode.cn/problems/find-the-duplicate-number/description/?envTypestudy-plan-v2envIdtop-100-liked
这题的思维难度较大。一种是利用双指针法进行计算环的起点这种方法在面试里很难说清楚也很难想到。大致做法就是定义快慢指针由于数字都是1-n一共n1个所以一定存在环。快慢指针一定会相遇但是相遇的点并不是重复数字的点所以再将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(leftright){int mid (leftright)/2;int count 0;for(int i0;inums.length;i){if(nums[i]mid){count; }}if(countmid)right mid;//midcount说明mid包括mid前面一定不存在重复的数字else left mid1;}return left;}
}
