LeetCode 寻找重复数【二分查找】【快慢指针】

╰半橙微兮° 2022-09-09 14:46 179阅读 0赞

# 1 寻找重复数 #

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
    
    假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。
    
    你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

输入：nums = [1,3,4,2,2]
    输出：2

示例 2：

输入：nums = [3,1,3,4,2]
    输出：3

示例 3：

输入：nums = [1,1]
    输出：1

示例 4：

输入：nums = [1,1,2]
    输出：1

提示：

1 <= n <= 105
    nums.length == n + 1
    1 <= nums[i] <= n
    nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

# 2 解决思路 #

## 2.1 Set ##

public int findDuplicate(int[] nums) { 
            Set<Integer> set = new HashSet<>();
            for (int num : nums) { 
                if (set.contains(num)) { 
                    return num;
                } else { 
                    set.add(num);
                }
            }
            return -1;
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_17_color_FFFFFF_t_70_g_se_x_16]

## 2.2 二分查找 ##

因为n+1个数组里面有1-n个数且必有一个重复的数，利用二分查找的特性，left=1，right=nums.length - 1，mid=(left + right) / 2，统计nums 中小于等于mid的数counts，如果counts<=mid，那么left=mid+1，如果counts>mid，right=mid，直至left=right。

public int findDuplicate2(int[] nums) { 
    
            int left = 1;
            int right = nums.length - 1;
    
            while (left <= right) { 
                int mid = (left + right) / 2;
                int count = 0;
                for (int num : nums) { 
                    if (num <= mid) { 
                        count++;
                    }
                }
                if (count <= mid) { 
                    left = mid + 1;
                } else { 
                    right = mid;
                }
                if (right == left) { 
                    return right;
                }
            }
            return -1;
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]

## 2.3 快慢指针 ##

把index理解成指针节点，把nums\[index\]理解成指针下个节点，慢指针一次走一步，快指针一次走2步，有题可知必成环。

public int findDuplicate3(int[] nums) { 
            int fast = 0;
            int slow = 0;
    
            do { 
                slow = nums[slow];
                fast = nums[nums[fast]];
            } while (slow != fast);
    
            int start = 0;
            int end = fast;
            while (start != end) { 
                start = nums[start];
                end = nums[end];
            }
            return start;
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/b9f63522cfad4907ba9e58579c6450f6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/476b0295786749e8ba275fc20add778f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/ddaba68a120c4bc49c2cbe9f09cd2d83.png