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

2023-12-22 19:43:22

题目链接: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;
    }
}

文章来源:https://blog.csdn.net/qq_45816864/article/details/135159107
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。