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

悠悠 2023-10-15 13:50 2阅读 0赞

**题目**

> 集合 `s` 包含从 `1` 到 `n` 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 **丢失了一个数字** 并且 **有一个数字重复** 。
> 
> 给定一个数组 `nums` 代表了集合 `S` 发生错误后的结果。
> 
> 请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
> 
> 难道: 简单
> 
> 题目
> 
> 链接：[645. 错误的集合][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循环，*外层循环遍历的是第一个元素，内层循环的初始条件就是第二个元素*

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

图解

![d0bcc51256d349eba68cf3c8c3a4bf21.png][]

**2. 求出缺失元素**

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

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

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

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

图解

![b7e02d8af68b4e8ca5e93584bc13431f.png][]

![e6aba88109834708905c5014d80417f6.png][]

[645.]: https://leetcode.cn/problems/set-mismatch/description/
[d0bcc51256d349eba68cf3c8c3a4bf21.png]: https://img-blog.csdnimg.cn/d0bcc51256d349eba68cf3c8c3a4bf21.png
[Leetcode_448.]: http://t.csdn.cn/a3IVq
[b7e02d8af68b4e8ca5e93584bc13431f.png]: https://img-blog.csdnimg.cn/b7e02d8af68b4e8ca5e93584bc13431f.png
[e6aba88109834708905c5014d80417f6.png]: https://img-blog.csdnimg.cn/e6aba88109834708905c5014d80417f6.png