【剑指offer|1.数组中重复的数字】

àì夳堔傛蜴生んèń 2024-03-24 15:32 51阅读 0赞

#### 文章目录 ####

*  0.数组中重复的数字
 *  1.堆排序
 *  2.修改数组的方法
 *  3.不修改数组的方法

## 0.数组中重复的数字 ##

![image-20230406123600476][]

> 关键字：
> 
> 1.  长度为n的数组nums中所有数字都在0~n-1范围内
> 2.  返回任意一个重复的数字

总体时间复杂度和空间复杂度分析：

![image-20230406180501569][]

## 1.堆排序 ##

void AdjustDown(vector<int>& nums,int n,int parent)
    {
        //
        int maxChild=2*parent+1;
        while(maxChild<n)
        {
            if(maxChild+1<n&&nums[maxChild]<nums[maxChild+1])
            {
                maxChild++;
            }
            if(nums[maxChild]>nums[parent])
            {
                swap(nums[maxChild],nums[parent]);
                parent=maxChild;
                maxChild=2*parent+1;
            }
            else 
            {
                break;
            }
        }
    }
    
    void HeapSort(vector<int>& nums)
    {
            //向下调整法建堆->错位相减法 ->logN
            int n=nums.size();
            for(int i=(n-1-1)/2;i>=0;i--)
            {
                AdjustDown(nums,n,i);
            }
    
            //类似删除法->完成排序
            int end=n;
            while(end>0)
            {
                swap(nums[0],nums[end-1]);
                end--;
                AdjustDown(nums,end,0);
            }
    }
    class Solution {
    public:
        int findRepeatNumber(vector<int>& nums) {
            //先进行堆排序,排升序 ->建立大堆
            HeapSort(nums);
            //排完序，比较前一个和后一个大小关系，相等则重复
            for(int i=1;i<nums.size();i++)
            {
                if(nums[i-1]==nums[i]) return nums[i];
            }
            return -1;
        }
    };

## 2.修改数组的方法 ##

> 修改数组的方法：  
> 因为有n个元素，每一个元素都在0~(n-1)范围内，如果元素不重复的话，  
> 对数组重排之后，下标和元素值之间应该是一一对应的关系  
> 但是因为重复的原因，重排之后，必然会导致一些下标对应的位置没有元素，一些下标对应的位置元素有多个  
> 只要找到重排之后下标对应的位置元素有多个的元素并返回即可。
> 
> 关键在于如何实现重排？
> 
> 现在我们重排这个数组：  
> 当扫描下标为i的数字m的时候，首先比较这个下标i是否等于数字m,如果等于就啥也不做，然后继续扫描下一个元素  
> 如果不等于就找到下标为m的位置：假设这个元素值为数字n：  
> 2.1如果相等，则说明这个位置重复了  
> 2.2如果不相等，则说明这个位置暂时还没有重复，把下标为i和下标为m的值进行交换；
> 
> 接下来重复以上步骤，直到找到第一个重复的元素即可

![image-20230406174346696][]

> C语言版：这里我原本犯了一个错，就是把//int m=nums\[i\]偷了一个懒，但是引发了一些bugs

//用m简写引发的bugs修正后的正确版本呢
    void swap(int* a,int* b)
    {
        int temp=*a;
        *a=*b;
        *b=temp;
    }
    int findRepeatNumber(int* nums, int numsSize){
        for(int i=0;i<numsSize;i++)
        {
            int m=nums[i];
            while(m!=i)
            {
                if(nums[m]==m)
                {
                    return m;
                }
                else
                {
                    //这里容易写bugs
                    //swap(&m,&nums[m]);
                    swap(&nums[i],&nums[m]);
                    m=nums[i];             
                }
            }
        }
        return -1;
    }
    
    void swap(int* a, int* b)
    {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    
    int findRepeatNumber(int* nums, int numsSize) {
        for (int i = 0; i < numsSize; i++)
        {
            //int m = nums[i];
            while (nums[i] != i)
            {
                if (nums[nums[i]] == nums[i])
                {
                    return nums[i];
                }
                else
                {
                    swap(&nums[i], &nums[nums[i]]);
                }
            }
        }
        return -1;
    }

## 3.不修改数组的方法 ##

![image-20230406123847158][]

> C语言：

int findRepeatNumber(int* nums, int numsSize){
        //int table[numsSize]={0};错误    ->不支持变长数组
        int* table=(int*)calloc(numsSize,sizeof(int));
        //malloc+memset=calloc    ->calloc的使用
        //int* table=(int*)malloc(sizeof(int)*numsSize);
        //memset(table,0,sizeof(int)*numsSize);
        
        for(int i=0;i<numsSize;i++)
        {
            table[nums[i]]++;
        }
        for(int i=0;i<numsSize;i++)
        {
            if(table[i]>1) return i;
        }
        return -1;
    }

> C++

class Solution {
    public:
        int findRepeatNumber(vector<int>& nums) {
            int n=nums.size();
            vector<int> table;
            table.resize(n,0);
            for(auto e : nums)
            {
                table[e]++;
            }
            for(auto e : nums)
            {
                //if(e>1) return e;错误
                if(table[e]>1) return e;//正确
            }
            return -1;
        }
    };

[image-20230406123600476]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/9f4e160d8fb54f1682c0a85d39a7fae8.png
[image-20230406180501569]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/65bf89aa7e5243c38f0b239572baee6e.png
[image-20230406174346696]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/8fb31ac6175a44b796d7a5019304db15.png
[image-20230406123847158]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/30b28dd4460446a29a2c1090e860cf3c.png