【題解】CSES - Missing Number

題目連結

題目大意

給定 $1 \sim n$ 的 $n - 1$ 個數字，問缺少哪一個？

• $2 \leq n \leq 2 \cdot 10^5$

題解

這邊提供兩種做法。
1. 開一個大小為 $n$ 的陣列紀錄每個數字是否出現過。

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<bool> have(n);
	for(int i = 0; i < n - 1; i++) {
		int x;
		cin >> x;
		x--;
		have[x] = true;
	}
	for(int i = 0; i < n; i++) {
		if(!have[i]) {
			cout << i + 1 << "\n";
			return 0;
		}
	}
	return 0;
}

2. 利用 xor 抵銷的性質 $a \oplus a = 0$，其中 $\oplus$ 是 bitwise xor。我們令 $b = \oplus_{i = 1}^{n} i$，對每個出現過的數字和 $b$ 取 xor 後剩下的就是缺少的了。

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	int ans = n;
	for(int i = 1; i < n; i++) {
		int x;
		cin >> x;
		ans ^= i;
		ans ^= x;
	}
	cout << ans << "\n";
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】CSES - Missing Number