[数据结构与算法]Leetcode每日刷题(day3)

每日鸡汤：🚀你必须非常努力，才能看起来毫不费力！

数组中重复的数字

来源：leetcode：剑指offer 03.数组中重复的数字

1、题目描述

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

2、示例

3、排序暴力求解

经历了四数之和的折磨，看到这道题目，我的内心是狂喜的，这算个题？四数之和截取的一部分就能解出来，快排一下，然后去重，so easy！😅

int cmp(const void* x,const void* y)
{
    return *(int*)x-*(int*)y;
}
int findRepeatNumber(int* nums, int numsSize)
{
    //排序后去枝叶
    int ret=0;
    qsort(nums,numsSize,sizeof(int),cmp);
    for(int i=0;i<numsSize;++i)
    {
        if(i>0&&nums[i]==nums[i-1])
        {
            ret=nums[i];
            break;
        }
    }
    return ret;
}

不得不说快排真的爽，我们来分析一下复杂度：

时间复杂度：大O一下就是O(N*logN)；

空间复杂度：O(1)

然后呢？跑是跑过去了，但是面试官问：不许用排序，有没有时间复杂度是O(N)，空间复杂度是O(1)的解法？果然，没那么简单。

4、交换比较解法

要求是O(N)，给我们的是数组，那么只有一种可能，最多遍历一遍数组就能找出重复的数。

我们再来看题目能不能给我们点有利的线索，我们注意到：

?这句话很重要！为什么呢？他告诉我们一个信息：如果数组内是有序的，且没有重复的数字，那么每个数的下标都应该和这个数相等！

大佬已经悟了，像我和各位老铁一样的普通码农可能还不太理解，我们进一步分析：

?对于这一组数，如何操作呢？

?图有点糙...

基本逻辑：

设i为下标遍历，数组为nums。

?i=0为下标遍历数组，如果i不等于以nums[i]，那么就把以nums[i]为下标的nums[nums[i]]和nums[i]比较，如果相等，就找到了重复的数字，如果不相等就交换，交换过后，继续比较i和nums[i]，如果相等，i就++，去查看下一个数，直到找到重复的数！

void Swap(int* x,int*y)
{
    int tmp=*x;
    *x=*y;
    *y=tmp;
}
int findRepeatNumber(int* nums, int numsSize)
{
    //注意数组长度为n，且所有数字都在0~n-1的范围内，所以如果没有重复的数，那么
    //如果排好序，必定每个数的下标都与这个数相等
    int ret=0;
    for(int i=0;i<numsSize;++i)
    {
        int flag=1;
        while(i!=nums[i])
        {
            //nums[nums[i]]和nums[i]比较
            if(nums[nums[i]]==nums[i])
            {
                ret=nums[i];
                flag=0;
                break;
            }
            else//如果不等于
            {
                Swap(&nums[nums[i]],&nums[i]);
            }
        }
        if(flag==0)
            break;
    }

复杂度分析：

代码中尽管有一个双重循环，但是每次交换都为一个数找到了它在有序数组里的正确位置可以减少我们后序循环。

时间复杂度：O(N)

空间复杂度：O(1)