魔法相册的重复记忆

题目分析

小红在整理魔法相册时,发现有些照片因为备份出现在了多个相册中。每张照片有唯一标识符和时间戳,同一相册内所有照片 ID 不同,但不同相册之间可能出现相同 ID 的照片(时间戳一定相同)。需要找出所有出现在超过一个相册中的照片,统计它们在所有相册中的总出现次数,并按时间戳升序输出。

思路

哈希表计数

遍历所有相册中的照片,用哈希表记录每个照片 ID 的:

  1. 时间戳:首次遇到时记录,后续不变(题目保证同 ID 时间戳相同)。
  2. 出现次数:每次遇到该 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(' '));
});

复杂度分析

  • 时间复杂度,其中 为所有相册中照片的总数。遍历所有照片 ,对重复照片排序最坏
  • 空间复杂度,哈希表存储所有照片信息。