20240121-集合不匹配

题目要求

您有一个整数集 s，其中原本包含从 1 到 n 的所有数字。不幸的是，由于某些错误，s 中的一个数字被复制到了整数集中的另一个数字上，导致一个数字重复，另一个数字丢失。

给你一个整数数组 nums，表示出错后这组数据的状态。

请找出重复出现的数字和丢失的数字，并以数组形式返回。

Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]

Example 2:

Input: nums = [1,1]
Output: [1,2]

思路

用一个map存储数字出现的次数，然后返回出现次数为0和2的数字。// 又好像不需要这么麻烦，从起始位置开始遍历，我们其实是知道每个位置需要出现的数字的。如果出现了不匹配的情况就可以知道谁重复、谁不见了。

但是数字排序的方式是未知的。这个问题的特点是，每个元素和数组索引有一定的对应关系。

我们现在自己改造下问题，暂且将?nums?中的元素变为?[0..N-1]，这样每个元素就和一个数组索引完全对应了，这样方便理解一些。

如果说?nums?中不存在重复元素和缺失元素，那么每个元素就和唯一一个索引值对应，对吧？

现在的问题是，有一个元素重复了，同时导致一个元素缺失了，这会产生什么现象呢？会导致有两个元素对应到了同一个索引，而且会有一个索引没有元素对应过去。

那么，如果我能够通过某些方法，找到这个重复对应的索引，不就是找到了那个重复元素么？找到那个没有元素对应的索引，不就是找到了那个缺失的元素了么？

那么，如何不使用额外空间判断某个索引有多少个元素对应呢？这就是这个问题的精妙之处了：

通过将每个索引对应的元素变成负数，以表示这个索引被对应过一次了。

如何同时寻找缺失和重复的元素 | labuladong 的算法笔记

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size();
        int dup = -1;
        for (int i = 0; i < n; ++i) {
            int index = abs(nums[i]) - 1;
            if (nums[index] < 0) {
                dup = abs(nums[i]);
            }
            else {
                nums[index] *= -1;
            }
        }
        int missing = -1;
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                missing = i + 1;
            }
        }
        return vector<int>{dup, missing};
    }
};