Leetcode题库442.数组中重复的数据(C实现)

• 思路
• 代码

1、遍历数组nums，并将每个数组值-1作为下标检索这个数组取得这个值将其加上numsSize

2、出现两次的数，将它作为下标检索出来的值一定>2numsSize，再遍历一次nums，将数组值大于2numsSize的下标找出来，加1放到nums数组的前面(因为之前减了1)，插入位置用flag标记，遍历完成后flag就是需要返回数组的长度，最后返回nums即可

3、为什么要加减1
减1：因为数组值在1 ~ n，而下标值在0 ~ n-1
加1：满足条件的下标是由原来数组值-1得到的
所以还原时需要加1

时间复杂度：O(n)
空间复杂度：O(1)

int* findDuplicates(int* nums, int numsSize, int* returnSize){
    int t=2*numsSize,flag=0,i;

    for(i=0;i
        if(nums[i]>t)
        nums[nums[i]-t-1]+=numsSize;
        else if(nums[i]>numsSize)
        nums[nums[i]-numsSize-1]+=numsSize;
        else
        nums[nums[i]-1]+=numsSize;
    }

    *returnSize=0;
    for(i=0;i
        if(nums[i]>t)
        nums[(*returnSize)++]=i+1;        
    }
    return nums;
}