魔法相册的重复记忆
题目分析
小红在整理魔法相册时,发现有些照片因为备份出现在了多个相册中。每张照片有唯一标识符和时间戳,同一相册内所有照片 ID 不同,但不同相册之间可能出现相同 ID 的照片(时间戳一定相同)。需要找出所有出现在超过一个相册中的照片,统计它们在所有相册中的总出现次数,并按时间戳升序输出。
思路
哈希表计数
遍历所有相册中的照片,用哈希表记录每个照片 ID 的:
- 时间戳:首次遇到时记录,后续不变(题目保证同 ID 时间戳相同)。
- 出现次数:每次遇到该 ID 就加 1。
遍历结束后,筛选出出现次数大于 1 的照片,按时间戳升序排序输出。
示例推演
输入 4 个相册:
- 相册 1:
999(ts=1) 998(ts=2) 997(ts=3) 996(ts=4) 995(ts=5) - 相册 2:
994(ts=6) 993(ts=7) 992(ts=8) 991(ts=9) 990(ts=10) - 相册 3:
989(ts=11) 988(ts=12) 987(ts=13) - 相册 4:
999(ts=1) 995(ts=5) 986(ts=14)
统计结果中出现次数 > 1 的:
- ID=999,时间戳=1,出现 2 次
- ID=995,时间戳=5,出现 2 次
按时间戳排序:999 2 995 2。
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
cin.ignore();
unordered_map<int, pair<int,int>> info; // id -> {timestamp, count}
for(int i = 0; i < n; i++){
string line;
getline(cin, line);
istringstream iss(line);
int id, ts;
while(iss >> id >> ts){
if(info.find(id) == info.end()){
info[id] = {ts, 1};
} else {
info[id].second++;
}
}
}
vector<tuple<int,int,int>> res; // (timestamp, id, count)
for(auto& [id, p] : info){
if(p.second > 1){
res.push_back({p.first, id, p.second});
}
}
sort(res.begin(), res.end());
for(int i = 0; i < (int)res.size(); i++){
if(i) cout << ' ';
cout << get<1>(res[i]) << ' ' << get<2>(res[i]);
}
cout << endl;
return 0;
}
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
Map<Integer, int[]> info = new HashMap<>(); // id -> [timestamp, count]
for (int i = 0; i < n; i++) {
String[] parts = br.readLine().trim().split("\\s+");
for (int j = 0; j + 1 < parts.length; j += 2) {
int id = Integer.parseInt(parts[j]);
int ts = Integer.parseInt(parts[j + 1]);
if (!info.containsKey(id)) {
info.put(id, new int[]{ts, 1});
} else {
info.get(id)[1]++;
}
}
}
List<int[]> res = new ArrayList<>();
for (Map.Entry<Integer, int[]> e : info.entrySet()) {
if (e.getValue()[1] > 1) {
res.add(new int[]{e.getValue()[0], e.getKey(), e.getValue()[1]});
}
}
res.sort((a, b) -> a[0] - b[0]);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < res.size(); i++) {
if (i > 0) sb.append(' ');
sb.append(res.get(i)[1]).append(' ').append(res.get(i)[2]);
}
System.out.println(sb.toString());
}
}
import sys
def main():
data = sys.stdin.read().split('\n')
idx = 0
n = int(data[idx]); idx += 1
info = {} # id -> [timestamp, count]
for i in range(n):
parts = data[idx].split(); idx += 1
j = 0
while j + 1 < len(parts):
pid = int(parts[j])
ts = int(parts[j + 1])
if pid not in info:
info[pid] = [ts, 1]
else:
info[pid][1] += 1
j += 2
res = []
for pid, (ts, cnt) in info.items():
if cnt > 1:
res.append((ts, pid, cnt))
res.sort()
print(' '.join(f"{pid} {cnt}" for ts, pid, cnt in res))
if __name__ == '__main__':
main()
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
let idx = 0;
const n = parseInt(lines[idx++]);
const info = new Map(); // id -> [timestamp, count]
for (let i = 0; i < n; i++) {
const parts = lines[idx++].split(/\s+/);
for (let j = 0; j + 1 < parts.length; j += 2) {
const id = parseInt(parts[j]);
const ts = parseInt(parts[j + 1]);
if (!info.has(id)) {
info.set(id, [ts, 1]);
} else {
info.get(id)[1]++;
}
}
}
const res = [];
for (const [id, [ts, cnt]] of info) {
if (cnt > 1) res.push([ts, id, cnt]);
}
res.sort((a, b) => a[0] - b[0]);
console.log(res.map(([ts, id, cnt]) => `${id} ${cnt}`).join(' '));
});
复杂度分析
- 时间复杂度:
,其中
为所有相册中照片的总数。遍历所有照片
,对重复照片排序最坏
。
- 空间复杂度:
,哈希表存储所有照片信息。

京公网安备 11010502036488号