南康市建设局网站,优惠券网站怎么做,wordpress 手机发博文,罗湖网站建设哪家好题目链接#xff1a;寻找重复数https://leetcode.cn/problems/find-the-duplicate-number/
方法一#xff1a;快慢指针
因为只有一个数字是重复的#xff0c;且一个数字正好对应一个唯一的下标#xff0c;所以可以将数组抽象为一个链表#xff0c;假定数组为{1,2,3,4,5,…题目链接寻找重复数https://leetcode.cn/problems/find-the-duplicate-number/
方法一快慢指针
因为只有一个数字是重复的且一个数字正好对应一个唯一的下标所以可以将数组抽象为一个链表假定数组为{1,2,3,4,5,6,3} -- {1,2,3,4,5,6},{3,4,5,6},{3,4,5,6}... slow一次走一步fast一次走两步那么当slow与fast相遇的时候必定是在环内的某一个位置假设slow走了n步fast就走了2n步。假设数组首部到环入口的距离为m那么slow在环内走了n-m的长度 fast走了2n-m个长度
则有 2n-m k(n-m) (k ! 0)
不妨设 n - m c 则可知 n%c 0
现在slow走了n-m步让slow再走m步就会到达环的入口(n%c 0),而m正是起点到环入口的距离。
代码
class Solution {
public:int findDuplicate(vectorint nums) {//快慢指针//当出现相同的数字时会形成类似于链表中的环。int fast 0,slow 0;while(true){fast nums[nums[fast]];//fast一次走两步slow nums[slow];//slow一次走一步if(fast slow)//两个节点下相遇必定是在环内部。break;}//当finder slow时就是环的入口//为什么finder和slow相遇的时候就是入口/*假定slow 和 fast 相遇时fast走了2n步slow走了n步 环长度为c 起点至环入口就是m则有n%c 0 n - m 为slow走的距离当slow再走一个m时就到环的入口而m正是起点到环入口的距离*/int finder 0;while(true){finder nums[finder];slow nums[slow];if(slow finder) break;}return slow;}
};
方法二二分查找
假定数组q[] {1,2,3,4,4} q.size 5 区间[1,4]
小于等于 1 的数字个数为 1 (1) 小于等于 2 的数字个数为 2 (1、2) 小于等于 3 的数字个数为 4 (1、2 、3) 小于等于 4 的数字个数为 4 (1、2、3、4、4)
可以看到左边的数集合严格小于自身右边的数集合严格大于自身。当集合中的个数cnt 指定的数字时就会出现重复数字。
二分的思想时当出现一个条件可以使得左半边的数字严格与右半边的数字出现分割就行。
class Solution {
public:int findDuplicate(vectorint nums) {int l 0,r nums.size()-1;while(l r){int mid l r 1;int cnt 0;for(int i 0;i nums.size();i){if(nums[i] mid){cnt;}}//当出现从cnt mid 就说明mid的左半部分出现了重复的数字使得计数大于mid//重复的数字在[l,mid]if(cnt mid) r mid;else l mid 1;}return l;}
};
