645. 错误的集合

Introduction

Question：645. 错误的集合

解法一

Analysis

由于数组中元素范围最大才到10^4，所以直接一个大数组来记录是否出现过即可。

Implement

vector<int> findErrorNums(vector<int>& nums) {
     vector<bool> vec(nums.size() + 1, false);
     int a, b;
     a = b = 0;
     for(auto i: nums) {
         if (vec[i]) {a = i;}
         vec[i] = true;
     }
     for(b = 1;b < vec.size() && vec[b]; b++);
     return {a, b};
}

解法二

Analysis

把数组与[1,2...,n]拼成一个大数组，这样就把问题转换成两个只出现过一次的元素了。即LC260-single-number-III。但是这样求解出来后是不知道顺序的，即无法区分哪个是重复的元素，哪个是丢失的元素，所有还需要再遍历一次数组来区分。

Implement

vector<int> findErrorNums1(vector<int>& nums) {
    int a = 0, b = 0;
    for(int i = 0;i < nums.size();i++) {
        a ^= nums[i];
        b ^= i + 1;
    }
    a ^= b;
    int mask = a & (-a);
    b = 0;
    for(int i = 0;i < nums.size(); i++) {
        if (nums[i] & mask) b ^= nums[i];
        if ((i+1) & mask) b ^= (i+1);
    }
    a = a ^ b;
    for(int i = 0;i < nums.size(); i++) {
        if (a == nums[i]) return {a, b};
    }
    return {b, a};
}