Leetcode: 645.错误的集合 题解【超详细】

题目

集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。

给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

难道: 简单

题目

链接：645. 错误的集合

示例 1：

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

示例 2：

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

提示：

• 2 <= nums.length <= 104
• 1 <= nums[i] <= 104

题目解析

根据题目我们可以知道 集合s [1,n]  里面是 有一个元素是重复的，有一个元素是缺失的,题目是要求我们返回数组的（即一个重复的元素，一个缺失的元素）。我们可以先求出重复的元素，再去求出缺失的元素。这个样子求解就比较简单。

代码展示

int* findErrorNums(int* nums, int numsSize, int* returnSize) {
    int* arr = (int*)malloc(sizeof(int) * 2);
    int i = 0; int j = 0;
    //找出复的数组元素
    for (i = 0; i < numsSize; i++)
    {
        for (j = i + 1; j < numsSize; j++)
        {
            if (nums[i] == nums[j])
            {
                arr[0] = nums[i];
            }
        }
    }
    //找出丢失的元素
    int arr2[10001] = { 0 };//创建临时数组
    //元素置零
    for (i = 0; i < numsSize; i++)
    {
        arr2[i] = 0;
    }
    int x = 0;
    for (i = 0; i < numsSize; i++)
    {
        x = nums[i] % (numsSize + 1);
        arr2[x - 1] = x;
    }
    j = 0;
    for (i = 1; i <= numsSize; i++)
    {
        if (arr2[i - 1] == 0)//遍历临时数组
        {
            arr[1] = i;
        }
    }
    *returnSize = 2;
    return arr;
}

 题目超详细解析

1.求出重复的元素

这里用的就是两层for循环，外层循环遍历的是第一个元素，内层循环的初始条件就是第二个元素

这是我们的思路就是 从第一个元素，进行与第二个元素、第三个元素进行比较；然后再让下一个元素与 下面的其他元素进行比较（直到找到重复的元素为止）

图解

2. 求出缺失元素 

 在这里求的缺失的元素是，简单思路就是 可以用一个临时数组（数组中的全部元素置0）来 把[ 1, n ] 这些数组元素存放到相应的数组中（就是与相应的数组下标与之对应）【例如】 元素 1 ，存放到临时数组 下标 1 中；元素 5 ，放到临时数组下标 5 中。

然后在 numsSize大小的数组中进行遍历 其中那个元素为零（因为只有1个元素是缺失的）就是缺失的数组。

这里如果上述文字表示很理解可以去看 

Leetcode:【448. 找到所有数组中消失的数字】题解

图解