LeetCode_二分搜索_双指针_中等_287.寻找重复数

落日映苍穹つ 2023-10-06 22:45 6阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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

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

**进阶：**  
如何证明 nums 中至少存在一个重复的数字?  
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/find-the-duplicate-number

## 2.思路 ##

（1）排序（不符合题目要求）  
如果只需保证空间复杂度为 O(1)，那么排序是一种比较容易想到的方法，即先对数组 nums 进行排序，然后再遍历该数组，在遍历的过程中判断每相邻的两个元素是否相等，找到后直接返回重复元素即可。但是本题还得保证**不修改数组 nums**，所以这种方法不行（下面的代码只是写出来练手，不符合题目要求）。

（2）二分搜索  
思路参考[本题官方题解][Link 1]。  
说实话，自己在写这道题的时候根本没有想到还可以使用二分搜索算法，这说明对二分搜索的掌握程度还有待提升！现在复习一下二分搜索：可以使用二分搜索的关键在于**能够从问题中抽象出一个自变量 x，一个关于 x 的函数 f(x) ，以及一个目标值 target，并且 f(x) 必须是在 x 定义域上的单调函数，题目是要求出 f(x) == target 时的 x 的值**。 以本题为例，它们的对应如下表所示：

<table> 
 <thead> 
  <tr> 
   <th>x</th> 
   <th>[1, n] 区间内的整数</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>f(x)</td> 
   <td>f(x) = cnt[x]，其中 cnt[x] 表示 nums 数组中小于等于 x 的数的个数，显然 cnt[x] 随 x 递增，即 f(x) 是单调函数</td> 
  </tr> 
  <tr> 
   <td>target</td> 
   <td>满足 target 前 cnt[i] ≤ i，target 后 cnt[i] &gt; i</td> 
  </tr> 
 </tbody> 
</table>

（3）快慢指针  
思路参考[本题官方题解][Link 1]以及[LeetCode\_双指针\_中等\_142.环形链表II][LeetCode_142._II]。

相关题目：  
[LeetCode\_双指针\_中等\_142.环形链表II][LeetCode_142._II]

## 3.代码实现（Java） ##

//思路1————排序(不符合题目要求)
    class Solution {
        
    	public int findDuplicate(int[] nums) {
        
    	    //对数组 nums 进行升序排序
    	    Arrays.sort(nums);
    	    int res = nums[0];
    	    for (int i = 1; i < nums.length; i++) {
        
    	        if (nums[i] != res) {
        
    	            res = nums[i];
    	        } else {
        
    	            return res;
    	        }
    	    }
    	    return res;
    	}    
    }

//思路2————二分搜索
    class Solution {
        
        public int findDuplicate(int[] nums) {
        
            int n = nums.length;
            int left = 1, right = n - 1;
            int res = -1;
            while (left <= right) {
        
                int mid = (left + right) / 2;
                /*
                    定义 cnt[i] 表示 nums 数组中小于等于 i 的数的个数
                    但由于只能使用常量级 O(1) 的额外空间，所以使用变量 cnt 记录每次统计的结果
                */
                int cnt = 0;
                //统计 nums 数组中小于等于 mid 的数的个数
                for (int i = 0; i < n; i++) {
        
                    if (nums[i] <= mid) {
        
                        cnt++;
                    }
                }
                /*
                    cnt <= mid:说明重复的整数在 [mid + 1, right] 区间中
                    cnt > mid:说明重复的整数在 [left, mid - 1] 区间中
                */
                if (cnt <= mid) {
        
                    left = mid + 1;
                } else {
        
                    right = mid - 1;
                    res = mid;
                }
            }
            return res;
        }
    }

//思路3————快慢指针
    class Solution {
        
    	public int findDuplicate(int[] nums) {
        
    		//定义快慢指针
    	    int slow = 0, 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;
    	}
    }

[Link 1]: https://leetcode.cn/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/
[LeetCode_142._II]: https://blog.csdn.net/weixin_43004044/article/details/122695166