leetcode[数组、双指针、二分搜索]寻找重复数（287）

1、问题描述

给定一个包含n&＃43;1个整数的数组nums&＃xff0c;其中&＃xff0c;每个整数的取值范围为[1&＃xff0c;n]&＃xff0c;根据鸽巢原理可知&＃xff0c;至少存在一个重复的整数。假设只有一个重复的数&＃xff0c;找出这个数。

2、解题思路

• 边界条件与特殊情况&＃xff1a;&＃xff08;1&＃xff09;nums中整数的个数小于2&＃xff1b;
• 问题分析&＃xff1a;以nums&＃61;[1&＃xff0c;3&＃xff0c;4&＃xff0c;2&＃xff0c;3]为例&＃xff0c;索引index的范围是在[0&＃xff0c;n]&＃xff0c;元素值value的范围是[1&＃xff0c;n]&＃xff0c;想象一下&＃xff0c;把数组看成一个链表&＃xff0c;数组中每一个位置上的元素值作为下一个元素的索引&＃xff0c;当有元素重复时&＃xff0c;会得到下面这样的带有环的索引链表&＃xff1a;
  

• 思路1&＃xff1a;根据上面的分析&＃xff0c;类比判断链表中是否存在环问题的解题思路&＃xff0c;采用快慢指针来解决这个问题&＃xff0c;整个思路分为两个步骤&＃xff1a;
• &＃xff08;1&＃xff09;检测环。具体地&＃xff0c;快、慢指针fast、slow都从0开始&＃xff0c;进行如下循环&＃xff1a;slow每次进行一跳&＃xff0c;而fast进行两跳&＃xff0c;比如&＃xff0c;一开始slow&＃61;i、fast&＃61;i&＃xff0c;下一步中&＃xff0c;slow&＃61;nums[i]&＃xff0c;而fast&＃61;nums[nums[i]]。当slow等于fast&＃xff0c;循环停止&＃xff0c;此时slow和fast都停在环上某个节点。
• &＃xff08;2&＃xff09;找到环的入口。具体地&＃xff0c;finder指针从0开始&＃xff0c;slow从上一步中slow和fast在环中的相遇的开始&＃xff0c;进行如下循环&＃xff1a;slow和finder指针每次都进行一跳。当finder等于fast时&＃xff0c;循环停止&＃xff0c;此时finder指向的为环的入口。
• 这里可能有点难理解的是&＃xff1a;为什么finder和slow会在环的入口处相遇&＃xff1f;我们可以证明一下&＃xff1a;
• 假设起点到环的入口处长度为m&＃xff0c;环的周长为c&＃xff0c;在检测环的过程中&＃xff0c;快慢指针在环中相遇&＃xff0c;此时&＃xff0c;fast走了2n步&＃xff0c;slow走了n步&＃xff0c;根据以上假设可得出以下结论&＃xff1a;
• 由于两个指针在环中相遇&＃xff0c;所以多走的n步一定是c的整数倍&＃xff0c;即n%c&＃61;0&＃xff1b;
• fast和slow相遇时&＃xff0c;slow在环中行走的距离是n-m&＃xff0c;此时&＃xff0c;若finder从起点开始&＃xff0c;slow从相遇点开始&＃xff0c;两者同步前进&＃xff0c;每次一步&＃xff0c;当finder走了m步到达环的入口处时&＃xff0c;slow走了n-m&＃43;m&＃61;n步&＃xff0c;而n又是c的整数倍&＃xff0c;故两者会在环的入口相遇。
• 先声明一下数据结构&＃xff1a;
• slow慢指针、fast快指针&＃xff0c;finder指针。
• 初始化&＃xff0c;一开始slow和fast都为0&＃xff0c;finder也为0
• 处理逻辑&＃xff1a; 检测环和找到环的入口。
• 这个方法的时间复杂度为$O(n)$&＃xff0c;空间复杂度为$O(1)$。
• 思路2&＃xff1a;一说到查找&＃xff0c;且时间复杂度小于O(n2)O(n^2)O(n2)&＃xff0c;则可以尝试二分查找&＃xff0c;二分查找的思路如下&＃xff1a;
• 由于数组的元素的取值范围在[1&＃xff0c;n]&＃xff0c;所以需要查找的数的区间也left&＃61;1、right&＃61;n&＃xff0c;取该区间的中位数mid&＃xff0c;统计数组中小于等于mid的元素个数count&＃xff0c;如果count<&＃61;mid&＃xff0c;则说明重复的整数在[mid&＃43;1&＃xff0c;right]区间&＃xff0c;否则在[left&＃xff0c;mid]之间&＃xff0c;如果left
• 由于进行了$logn$次查找&＃xff0c;统计小于mid的元素个数count时间复杂度为$O(n)$&＃xff0c;所以时间复杂度为$O(nlogn)$&＃xff0c;空间复杂度为$O(1)$。

3、代码实现

快慢指针实现&＃xff1a;

class Solution {
public:int findDuplicate(vector<int>& nums) {if (nums.size() < 2){return 0;}int slow&＃61;0;int fast &＃61; 0;int finder &＃61; 0;while(true){slow &＃61; nums[slow];fast &＃61; nums[nums[fast]];if(slow &＃61;&＃61; fast){break;}}while(true){slow &＃61; nums[slow];finder &＃61; nums[finder];if(slow &＃61;&＃61; finder){break;}}return finder;}
};


二分搜索实现&＃xff1a;

class Solution {
public:int findDuplicate(vector<int>& nums) {if (nums.size() < 2){return 0;}int left &＃61; 1;int right &＃61; nums.size() - 1;while(left < right){int mid &＃61; (left &＃43; right) /2;int count &＃61; countNums(nums,mid);if(count <&＃61; mid){left &＃61; mid &＃43; 1;}else{right &＃61; mid;}}return left;}int countNums(vector<int>& nums,int e){int count &＃61; 0;for(int i&＃61;0;i<nums.size();i&＃43;&＃43;){if(nums[i] <&＃61; e){count &＃43;&＃43;;}}return count;}
};