Official
C - Centers Editorial by yuto1115
解説以下のアルゴリズムによって解くことができます。
- 空の配列 \(ans\) を用意する。
- \(A_1,A_2,\dots\) の順に数列を走査する。このとき、今まで見た部分の中に各数字が何回現れたかを別の配列で管理しておく。今見ている数字を \(c\) としたとき、\(c\) が現れたのが \(2\) 回目であるならば、\(ans\) の末尾に \(c\) を追加する。
- \(ans\) を出力する。
このアルゴリズムは \(O(N)\) で動作し、十分高速です。
実装例 (C++) :
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> cnt(n + 1), ans;
for (int i = 0; i < 3 * n; i++) {
int a;
cin >> a;
++cnt[a];
if (cnt[a] == 2) ans.push_back(a);
}
for (int i = 0; i < n; i++) {
cout << ans[i] << (i == n - 1 ? '\n' : ' ');
}
}
実装例 (Python) :
n = int(input())
a = list(map(int, input().split()))
cnt = [0 for _ in range(3 * n)]
ans = []
for i in a:
cnt[i] += 1
if cnt[i] == 2:
ans.append(i)
print(*ans)
posted:
last update: