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

MicroFrank

发布于 2023-04-07 19:03:23

1620

发布于 2023-04-07 19:03:23

文章被收录于专栏：同步文章1234同步文章1234

文章目录

0.数组中重复的数字

关键字：

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

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

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的值进行交换；接下来重复以上步骤，直到找到第一个重复的元素即可

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.不修改数组的方法

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;
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2023-04-06，如有侵权请联系 cloudcommunity@tencent.com 删除

c++