Lỗi trùng lặp trong tập hợp (Set Mismatch) trong C++

Mô tả bài toán

Tập hợp S ban đầu chứa 1..n. Do lỗi, một số bị trùng lặp ghi đè số khác. Cho mảng nums trạng thái sau lỗi. Tìm số bị trùng và số bị thiếu.

Ví dụ: [1,2,3,4,4,6] → Trùng 4, thiếu 5 → [4,5].

Giải pháp (Đánh dấu âm + Toán học)

• Tính tổng thực tế s1 và tổng kỳ vọng exp_sum = n(n+1)/2.
• Duyệt mảng, đánh dấu nums[abs(nums[i])-1] âm. Nếu đã âm → đó là số trùng dup = abs(nums[i]).
• Số thiếu = dup - (s1 - exp_sum).

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v) {
    cout << "[";
    for (int x : v) cout << x << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> findErrorNums(vector<int>& A) {
        vector<int> v(2);
        long long s1 = accumulate(A.begin(), A.end(), 0LL);
        int n = A.size();
        long long exp_sum = 1LL * n * (n + 1) / 2;
        for (int i = 0; i < n; i++) {
            int idx = abs(A[i]) - 1;
            if (A[idx] > 0) A[idx] = -A[idx];
            else { v[0] = abs(A[i]); break; }
        }
        v[1] = v[0] - (s1 - exp_sum);
        return v;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,3,4,4,6};
    print_vector(ob.findErrorNums(v));
    return 0;
}

Đầu vào

{1,2,3,4,4,6}

Đầu ra

[4, 5, ]