力扣思维题——寻找重复数
2023-12-22 19:43:22
这题的思维难度较大。一种是利用双指针法进行计算环的起点,这种方法在面试里很难说清楚,也很难想到。大致做法就是,定义快慢指针,由于数字都是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;
}
}
文章来源:https://blog.csdn.net/qq_45816864/article/details/135159107
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!