LeetCode 287. 寻找重复数

向右看齐 2022-10-26 04:00 159阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70 1]

//解法一：排序+二分 自己写的  好慢。。。。
    class Solution {
        
        public int findDuplicate(int[] nums) {
        
            Arrays.sort(nums);
            for(int i = 0; i < nums.length; i++)
                System.out.print(nums[i] + " ");
            int n = nums.length;
            int l = 0;
            int r = n - 1;
            while(l < r){
        
                int mid = l + r>> 1;
                if(nums[mid] <= mid)
                    r = mid;
                else
                    l = mid + 1;
            }
            return nums[l];
        }
    }

//解法二：才58%
    //https://leetcode-cn.com/problems/find-the-duplicate-number/solution/er-fen-fa-si-lu-ji-dai-ma-python-by-liweiwei1419/
    public class Solution {
        
    
        public int findDuplicate(int[] nums) {
        
            int len = nums.length;
            int left = 1;
            int right = len - 1;
            while (left < right) {
        
                // 在 Java 里可以这么用，当 left + right 溢出的时候，无符号右移保证结果依然正确
                int mid = (left + right) >>> 1;
                
                int cnt = 0;
                for (int num : nums) {
        
                    if (num <= mid) {
        
                        cnt += 1;
                    }
                }
    
                // 根据抽屉原理，小于等于 4 的个数如果严格大于 4 个
                // 此时重复元素一定出现在 [1, 4] 区间里
                if (cnt > mid) {
        
                    // 重复元素位于区间 [left, mid]
                    right = mid;
                } else {
        
                    // if 分析正确了以后，else 搜索的区间就是 if 的反面
                    // [mid + 1, right]
                    left = mid + 1;
                }
            }
            return left;
        }
    }

//解法三：快慢指针 这才是最快的！！！！！！！
    //快的走两格，慢的走一个，相遇的话将慢的置为0，之后快慢指针都直走一格，再次相遇就是答案
    //https://leetcode-cn.com/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/
    class Solution {
        
        public int findDuplicate(int[] nums) {
        
            int slow = 0;
            int fast = 0;
            do{
        
                slow = nums[slow];
                fast = nums[nums[fast]];
            }while(slow != fast);
            slow = 0;
            while(slow != fast){
        
                slow = nums[slow];
                fast = nums[fast];
            }
            return slow;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2021020119580169.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70 1]: /images/20221024/aa9833693c724d7f8d4d75cb286e3d0e.png