leetcode day7 442

442 数组重复出现的数据

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 最多两次 。请你找出所有出现 两次 的整数，并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间（不包括存储输出所需的空间）的算法解决此问题。

示例 1：

输入：nums = [4,3,2,7,8,2,3,1]
输出：[2,3]
示例 2：

输入：nums = [1,1,2]
输出：[1]
示例 3：

输入：nums = [1]
输出：[]
 

解题思路：将元素交换到对应的位置。

将数 i 放在数组中下标为 i−1 的位置：

（1）如果 i 恰好出现了一次，那么将 i 放在数组中下标为 i−1 的位置即可；
（2）如果 i 出现了两次，将另一个 i 放置在任意不冲突的位置 j，数 j+1 没有在数组中出现过。
如果 nums[i]−1！=i，说明 nums[i] 出现了两次（另一次出现在位置 num[i]−1）

放置的方法：对数组进行一次遍历。当遍历到位置 i 时，nums[i] 应该被放在位置 nums[i]−1。不满足交换 num[i] 和 nums[nums[i]−1] 即可，直到待交换的两个元素相等为止。

int* findDuplicates(int* nums, int numsSize, int* returnSize) {
    int *a=(int*)malloc(sizeof(int)*numsSize);
    *returnSize=0;
    for(int i=0;i<numsSize;i++){
        while(nums[i]!=nums[nums[i]-1]){
            int t=nums[i];
            nums[i]=nums[t-1];
            nums[t-1]=t;
        }
    }
    for(int i;i<numsSize;i++){
        if(nums[i]-1!=i){
            a[(*returnSize)++]=nums[i];
        }
    }
    return a;
}

本题如果不要求使用常量额外空间，我们可以简单的遍历数组，并使用哈希表存储每个正整数然后再找出出现两次的数。

int* findDuplicates(int* nums, int numsSize, int* returnSize) {
    int *a=(int*)malloc(sizeof(int)*numsSize);
    int b[100005]={},k=0;
    *returnSize=0;
    for(int i=0;i<numsSize;i++){
         b[nums[i]]++;
         if( b[nums[i]]==2){
            a[k]=nums[i];
            k++;
         }
    }
    *returnSize=k;
    return a;
}