題目簡介

• 題源：1035-Sign in | CCUT OJ，2014 吉林省賽 C 題
• 題意：給定長為 \(n\) 的序列 \(A\) 與長為 \(n-1\) 的序列 \(B\)，其中 \(B\subset A\)，求 \(A-B\)。即：\(B\) 中恰好只有一個元素在 \(A\) 中沒出現(xiàn)，求這個元素。
• 數(shù)據(jù)范圍：\(1\le n\le 10^5\)，序列值域：\(0\le R\le 10^8\)
• 注：若無特殊說明，博主的代碼模板如下，通過solve函數(shù)處理多組測試用例。本文后續(xù)代碼僅給出solve函數(shù)。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define ln '\n'

int solve(){

}

int main(){
	int T;cin>>T;
	while(T--){
		printf("Team %08d didn't sign in!\n",solve());
	}
	return 0;
}

題解

樸素想法

最樸素的想法：雙層for循環(huán)枚舉匹配，若未找到則輸出該項。時間復(fù)雜度\(O(n^2)\)，超時。

void solve(){
	int n;cin >> n;
	vector<int> a(n);
	vector<int> b(n-1);
	for (auto &i:a) cin >> i;
	for (auto &i:b) cin >> i;
	int ans = -1;
	for (int i = 0; i < n; i++) {
	    bool ok = 0;
	    for (int j = 0; j < n-1; j++) {
	        if (a[i] == b[j]) {
	            ok = 1;
	            break;
	        }
	    }
	    if (!ok) {
	        ans = a[i];
	        break;
	    }
	}
	return ans;
}

方法1：哈希表

如果你學(xué)過 C++，那么可用 unordered_map 一發(fā)AC。

int solve(){
	int n;cin >> n;
	vector<int> a(n);
	unordered_set<int> b;
	for (auto &i:a) cin >> i;
	for (int i = 0; i < n - 1; i++) {
	    int _;cin >> _;
	    b.insert(_);
	}
	int ans = -1;
	for (int i = 0; i < n; i++) {
	    if (!b.count(a[i])) {
	        ans = a[i];
	        break;
	    }
	}
	return ans;
}

方法2：排序

按升序排序后，再逐項比較。注意應(yīng)選擇 \(O(n\cdot \log n)\) 復(fù)雜度的排序算法，否則將退化為暴力。

int solve(){
	int n;cin >> n;
	vector<int> a(n);
	vector<int> b(n-1);
	for (auto &i:a) cin >> i;
	for (auto &i:b) cin >> i;
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	int ans = a[n-1];
	for (int i = 0; i < n-1; i++) {
	    if (a[i] != b[i]) {
	        ans = a[i];
	        break;
	    }
	}
	return ans;
}

方法3：異或

異或具有如下性質(zhì)：\(a\oplus a=0,a\oplus 0=a\)。因此考慮對 \(A\) 中每個元素進(jìn)行異或，再對 \(B\) 中每個元素進(jìn)行異或。出現(xiàn)兩次的元素會變?yōu)?\(0\)，剩下的那個數(shù)就是只出現(xiàn)一次的數(shù)。

int solve(){
	int n;cin >> n;
	int ans =0;
	for (int i = 0; i < n; i++) {
	    int _;cin>>_;
	    ans ^= _;
	}
	
	for (int i = 0; i < n-1; i++) {
	    int _;cin >> _;
	    ans ^= _;
	}
	return ans;
}