系列文章目录
力扣热题刷题记录
文章目录
系列文章目录前言一、背景二、我的思路三、官方的思路
1.二进制位法2.快慢指针3.二分法 总结 前言
每天进步一点点！！
一、背景
来源：力扣
链接：https://leetcode-cn.com/problems/find-the-duplicate-number/
注意审题：
第一，不允许修改数组，所以不能用排序做；
第二，只能用常数个空间，故而不能用哈希，也不能开辟另一个数组存储数的个数；
由此，发现很容易想到的就是暴力求解，对于每一个数，都去跟后面的数进行比较，但这样容易超时。
二、我的思路
我没有思路啊啊，我的思路都被题目限制掉了，我去！！！
三、官方的思路 1.二进制位法
class Solution {public: int findDuplicate(vector& nums) { //采用二进制位的办法 //如果对于重复的数字（把它展开为对应的二进制） //它相比统计（1-n）第i位的1个数会更大 //如果重复数字的第i位是0,，不用管，不影响 //如果重复数字的第i位是1，那么x>y //举例，1,2,3,和1,2,2，（1-3）的第二位为1加起来的和y=2 //而1,2,2,有重复数字的第二位加起来的和x=3,由此x>y //实际上对于每一位都是如此，只要他当前位是1，我就可以累计求和 //具体还原就是，满足x>y，说明当前位是重复数字的1位 //因为当前位是0，不考虑是因为，一是它不满足x>y的条件，二是它是0位，加上去没意义 int bitMax=31;//由于int最大数最高位是31位，而提示说了，最大数是n<=10000<2^31 int len = nums.size();//len=n+1，题目有的 //用最大数n（即len-1）去右移，直到移到最高位，满足 " !1=false "，跳出循环 while (!(len-1)>>bitMax) { bitMax-=1; } int ans=0; //用于记录最后的结果，即重复数 //bit 循环用于移位，从而计算每一位，第一次移动0位，第二次1位…… for (int bit=0;bit <=bitMax; bit++) { int x=0,y=0;//x用于统计实际某位为1的总数，y用于统计1-n的某位为1的总数 for (int i=0;i=1(统计的是1-n之间)， //并且 i 与第bit位的1进行与运算得到结果为1，统计Y if (i>=1 && (i & (1<y,说明当前这个bit为是属于重复数当中的某一位 //然后需要累加起来,用或运算，因为ans初始所有位为0 if(x>y) { ans = ans | (1<
2.快慢指针
class Solution {public: int findDuplicate(vector& nums) { //看了快慢指针的思路，现在来开始编码 //首先如果有一个数字重复，按照把nums[i]和index都看成索引，就可构建环 //有了环之后，其它没构建的就不用管它了，因为题目说了只有一个重复数 //第一步，构建环，第二步找到环的入口（重复数） //此时把快指针重新放入起点（相遇时，快指针比慢指针多走了2n-n=n步） //设环的周长为C,则n%c==0（因为n步都用在了绕环上面），然后起点到环的入口m //慢指针的位置为环的入口开始走了n-m，再走m步就可以到达环入口， //所以最后相遇点就是重复数 int fast=0,low=0;//定义快慢指针，其为数组的索引 //相遇时停止 while (nums[low]!=nums[fast] || fast==0 ) { //慢指针一步，然后快指针两步 low = nums[low]; fast = nums[fast]; fast = nums[fast]; } //cout<<"相遇时fast "<
3.二分法
注意，原来的二分是针对数组有序，根据要搜的值和数组中间的值进行比较，依次对半对半排除。
而这里的用法，是它的稍微变化。也就是说，不一定是比较数组的值，而是可以比较另一个变量，只要这个变量满足一定的条件即可。
具体解释如下：
class Solution {public: int findDuplicate(vector& nums) { //排个序，重复的数字一定聚集在一起 //但是不修改数组，故而不能排序 int n = nums.size(); int l = 1, r = n - 1, ans = -1; while (l <= r) { int mid = (l + r) >> 1;//右移除以2，找寻中点 int cnt = 0; for (int i = 0; i < n; ++i) { //假设mid就是要找的那个数，然后统计cnt， //如果mid真的是目标数，会符合规律cnt>mid，所以就能求解 cnt += (nums[i] <= mid); } if (cnt <= mid) { l = mid + 1; } else { r = mid - 1; ans = mid; } } return ans; }};
总结
这几个解法都比较难想，也不容易被理解，大家用心慢慢看就可以了，我也是看了好几天，呜呜呜！