力扣热题刷题记录
文章目录系列文章目录前言一、背景二、我的思路三、官方的思路
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;
}
};
总结
这几个解法都比较难想，也不容易被理解，大家用心慢慢看就可以了，我也是看了好几天，呜呜呜！
