leetcode——“数组中重复的数据” 详解

链接如下:

442. 数组中重复的数据

题目:

leetcode——“数组中重复的数据” 详解_第1张图片

方法一:将元素交换到对应位置

void swap(int* pa,int* pb)
{
    int tmp=*pa;
    *pa=*pb;
    *pb=tmp;
}
int* findDuplicates(int* nums, int numsSize, int* returnSize){
    int i=0;
    int j=0;
    for(i=0;i< numsSize;i++)    //走 numsSize 趟
    {
        while(nums[i]!=nums[nums[i]-1])   
        {
            swap(&nums[i],&nums[nums[i]-1]);
        }
    }
    int* ans=(int*)malloc(sizeof(int)* numsSize);
    for(i=0;i< numsSize;i++)
    {
        if(nums[i]!=i+1)
        {
            ans[j++]=nums[i];
        }
    }
    * returnSize=j;
    return ans;
}

 通过第一个for循环将每一个数放在对应的位置。由于数组的下标范围是 [0, n-1],我们需要将数 i 放在数组中下标为 i−1 的位置:

●如果i恰好出现了一次,那么将i放在数组中下标为i- 1的位置即可;
●如果i出现了两次,只要其中的一个 i 放在数组下标中为i- 1的位置, 另一个i放置在任意的位置,假设下标是 j ,也就是说数 j+ 1没有在数组中出现过。
举个例子:4,3,2,7,8,2,3,1  经历第一次for循环后就会变成:     1 2 3 4 3 2 7 8        

所以这样放置完一遍后, 那么我们只需要对数组进行一次遍历。当遍历到位置 i 时,如果nums[i] ≠ i+1,说明nums[i]出现了两次(另一次出现在num[ num[i]- 1 ] ),我们就可以将num[i]放入答案。

自己malloc一个需要返回的数组ans,我们先开 numsSize 个整形大小,作为返回值的数组不算在额外开辟的空间中,所以空间复杂度依旧符合O(1),比如上面已经放置后的 1 2 3 4 3 2 7 8   ,nums[4] != 5,说明nums[4] 这个值出现了2次,直接把nums[4] 赋值给 数组ans,并用 j 记录ans下标大小,赋值完后 j 就是数组ans的大小,* returnSize=j;   return ans; 即可。

单独讲一下第一个for:

   for(i=0;i< numsSize;i++)   
    {
        while(nums[i]!=nums[nums[i]-1])   
        {
            swap(&nums[i],&nums[nums[i]-1]);
        }
    }

 走 numsSize 趟,每趟把nums[i]这个数放到他对应的下标的位置nums[nums[i]-1],nums[i]和nums[nums[i]-1]相等停下的条件有2个:如果nums[i]恰好就是在他应该在的下标的位置就不用进行了 或者 nums[i]和对应下标位置nums[nums[i]-1]是重复数字也停下,经过 numsSize 趟,就会把所有nums[i] 放进对应位置,重复的数字有一个在对应位置,另一个在缺失数字的位置。

动态图过程)此动图只做到了i=3,仅助于大家理解

leetcode——“数组中重复的数据” 详解_第2张图片

 

你可能感兴趣的