【重点】【二分查找】287.寻找重复数

题目2种方法都要理解掌握最简单的基于HashSet的就不写在下面了过于简单了。一道类似的 题目对比学习0n-1中缺失的数字法1二分查找O(nlogn)时间复杂度O(nlogn)PythonclassSolution:deffindDuplicate(self,nums:List[int])-int:l,r1,len(nums)-1# l和r分别是起始数字1和n, 不是索引whilelr:mid(lr)//2count0foriinnums:ifimid:count1ifcountmid:# 这种情况重复的数字一定大于mid!lmid1else:# 有可能重复的数字是midrmidreturnlJava必须熟练掌握classSolution{publicintfindDuplicate(int[]nums){intnnums.length;intleft1,rightn;// 1和n是数字与数组索引无关while(leftright){intmidleft(right-left)/2;intcount0;for(inti:nums){if(imid){count;}}if(countmid){// 这种情况重复的数字一定大于mid!leftmid1;}else{// 有可能重复的数字是midrightmid;}}returnleft;}}法2环形链表参考答案classSolution{publicintfindDuplicate(int[]nums){intslow0,fast0;do{slownext(nums,slow);fastnext(nums,next(nums,fast));}while(slow!fast);slow0;while(slow!fast){slownext(nums,slow);fastnext(nums,fast);}returnslow;}publicintnext(int[]nums,intinx){returnnums[inx];}}