题目简介
- 题源：1035-Sign in | CCUT OJ，2014 吉林省赛 C 题
- 题意：给定长为 \(n\) 的序列 \(A\) 与长为 \(n-1\) 的序列 \(B\)，其中 \(B\subset A\)，求 \(A-B\)。即：\(B\) 中恰好只有一个元素在 \(A\) 中没出现，求这个元素。
- 数据范围：\(1\le n\le 10^5\)，序列值域：\(0\le R\le 10^8\)
- 注：若无特殊说明，博主的代码模板如下，通过
solve函数处理多组测试用例。本文后续代码仅给出solve函数。
#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循环枚举匹配，若未找到则输出该项。时间复杂度\(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：哈希表
如果你学过 C++，那么可用 unordered_map 一发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：排序
按升序排序后，再逐项比较。注意应选择 \(O(n\cdot \log n)\) 复杂度的排序算法，否则将退化为暴力。
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：异或
异或具有如下性质：\(a\oplus a=0,a\oplus 0=a\)。因此考虑对 \(A\) 中每个元素进行异或，再对 \(B\) 中每个元素进行异或。出现两次的元素会变为 \(0\)，剩下的那个数就是只出现一次的数。
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;
}