每日一题-7th

⭐每日一题⭐专栏

written by SJTU-XHW

本人学识有限，解析难免有错，恳请读者能够批评指正，本人将不胜感激！

Leetcode 645. 错误的集合

题干

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

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

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

示例

示例 1：

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

示例 2：

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

思路

不难发现此题的思路之一是可以借鉴 “只出现一次数字” 的题目的思路，将1~n的数据和当前集合合并成一个集合，则问题转化为：集合中1~n元素除了有两个元素，一个出现3次，一个出现1次，其余的一个出现2次。找出出现次数不是两次的那两个元素。

实现

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int len = nums.size();
        int model = 0, nsum = 0;
        for (int i = 0; i < len; ++i) { model ^= nums[i]; nsum += nums[i]; }
        for (int i = 1; i <= len; ++i) model ^= i;
        int diffIdx = 1;
           for (; (model & diffIdx) == 0; diffIdx <<= 1);
        int a = 0, b = 0;
        for (int i = 0; i < len; ++i) {
            if (nums[i] & diffIdx) a ^= nums[i];
            else b ^= nums[i];
        }
        for (int i = 1; i <= len; ++i) {
            if (i & diffIdx) a ^= i;
            else b ^= i;
        }
        int maxa = (a > b ? a : b), mina = (a < b ? a : b);
        vector<int> ans;
        if (nsum > len * (len + 1) / 2.0)
            { ans.push_back(maxa); ans.push_back(mina); }
        else { ans.push_back(mina); ans.push_back(maxa); }
        return ans;
    }
};