#P4549. 第1题-相册重复图片检测
-
1000ms
Tried: 60
Accepted: 13
Difficulty: 5
所属公司 :
华为
时间 :2026年1月21日-非AI方向(通软&嵌软&测试&算法&数据科学)
-
算法标签>哈希表
第1题-相册重复图片检测
解题思路
-
每个相册内无重复照片,不同相册间可能出现同一照片(以照片 id 相同为重复)。
-
读取 N 个相册中每张照片的
(id, 时间戳):- 用哈希表统计每个
id出现于多少个相册(因为同一相册内不重复,直接累加即可)。 - 同时记录该
id的时间戳(题目数据保证输出唯一;实现上可记录第一次出现的时间戳)。
- 用哈希表统计每个
-
最后筛出
count > 1的id,按(时间戳升序, id升序)排序(用 id 作兜底保证稳定),输出id 重复次数的序列。
涉及算法:哈希表统计 + 排序。
复杂度分析
设总照片数为 K(所有相册照片数之和,K ≤ 10 * 100 = 1000):
- 时间复杂度:
O(K + D log D),其中D为重复照片个数。 - 空间复杂度:
O(K)(哈希表存储统计信息)。
代码实现
import sys
def detect_duplicates(album_lines):
# 哈希表:id -> [出现次数, 时间戳]
mp = {}
for line in album_lines:
arr = list(map(int, line.strip().split()))
# 每行是 2M 个数字,按 (id, ts) 成对读取
for i in range(0, len(arr), 2):
pid = arr[i]
ts = arr[i + 1]
if pid not in mp:
mp[pid] = [1, ts]
else:
mp[pid][0] += 1
res = []
for pid, (cnt, ts) in mp.items():
if cnt > 1:
res.append((ts, pid, cnt))
# 按时间戳升序;时间戳相同用 id 升序兜底
res.sort()
# 组织输出为 id count id count ...
out = []
for _, pid, cnt in res:
out.append(str(pid))
out.append(str(cnt))
return " ".join(out)
def main():
data = sys.stdin.read().splitlines()
if not data:
return
n = int(data[0].strip())
album_lines = data[1:1 + n]
ans = detect_duplicates(album_lines)
sys.stdout.write(ans)
if __name__ == "__main__":
main()
#include <bits/stdc++.h>
using namespace std;
// 题面功能:检测跨相册重复图片,返回 (id, count) 序列字符串
string detectDuplicates(const vector<string>& albumLines) {
// 哈希表:id -> {count, timestamp}
unordered_map<int, pair<int,int>> mp;
for (const string& line : albumLines) {
stringstream ss(line);
int id, ts;
// 每行按 (id, ts) 成对读取
while (ss >> id >> ts) {
auto it = mp.find(id);
if (it == mp.end()) {
mp[id] = {1, ts};
} else {
it->second.first += 1; // 出现次数加一
}
}
}
// 收集重复项:{ts, id, count}
vector<tuple<int,int,int>> vec;
for (auto &kv : mp) {
int id = kv.first;
int cnt = kv.second.first;
int ts = kv.second.second;
if (cnt > 1) vec.push_back(make_tuple(ts, id, cnt));
}
// 按时间戳升序;相同时间戳按 id 升序
sort(vec.begin(), vec.end(), [](const auto& a, const auto& b){
if (get<0>(a) != get<0>(b)) return get<0>(a) < get<0>(b);
return get<1>(a) < get<1>(b);
});
// 组织输出
stringstream out;
for (int i = 0; i < (int)vec.size(); i++) {
if (i) out << ' ';
out << get<1>(vec[i]) << ' ' << get<2>(vec[i]); // 输出 id count
}
return out.str();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
string dummy;
getline(cin, dummy); // 吃掉行尾换行
vector<string> albumLines;
albumLines.reserve(N);
for (int i = 0; i < N; i++) {
string line;
getline(cin, line);
albumLines.push_back(line);
}
cout << detectDuplicates(albumLines);
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
// 题面功能:检测跨相册重复图片,返回输出字符串
static String detectDuplicates(List<String> albumLines) {
// 哈希表:id -> [count, timestamp]
HashMap<Integer, int[]> map = new HashMap<Integer, int[]>();
for (String line : albumLines) {
line = line.trim();
if (line.length() == 0) continue;
String[] parts = line.split("\\s+");
// 每行是 (id, ts) 成对出现
for (int i = 0; i < parts.length; i += 2) {
int id = Integer.parseInt(parts[i]);
int ts = Integer.parseInt(parts[i + 1]);
int[] val = map.get(id);
if (val == null) {
map.put(id, new int[]{1, ts});
} else {
val[0] += 1; // 出现次数加一
}
}
}
// 收集重复项:用数组保存 [ts, id, count]
ArrayList<int[]> list = new ArrayList<int[]>();
for (Map.Entry<Integer, int[]> e : map.entrySet()) {
int id = e.getKey();
int cnt = e.getValue()[0];
int ts = e.getValue()[1];
if (cnt > 1) {
list.add(new int[]{ts, id, cnt});
}
}
// 按时间戳升序;相同时间戳按 id 升序
Collections.sort(list, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
if (a[0] != b[0]) return a[0] - b[0];
return a[1] - b[1];
}
});
StringBuilder sb = new StringBuilder();
for (int i = 0; i < list.size(); i++) {
int[] x = list.get(i);
if (sb.length() > 0) sb.append(' ');
sb.append(x[1]).append(' ').append(x[2]); // 输出 id count
}
return sb.toString();
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String first = br.readLine();
if (first == null || first.trim().length() == 0) return;
int n = Integer.parseInt(first.trim());
List<String> albumLines = new ArrayList<String>();
for (int i = 0; i < n; i++) {
albumLines.add(br.readLine());
}
String ans = detectDuplicates(albumLines);
System.out.print(ans);
}
}
题目描述
手机里有一系列图片,它们会被分类到不同的相册中去。同一个相册内无重复图片,不同相册间可能有重复图片出现。所有相册里的照片都是以时间升序排列的。现在给定 N 个相册内的图片序列,请输出在不同相册重复出现的图片,并把它们对的重复出现次数。输出也需要按照时间升序排列。不同图片的时间戳可能相同,但输入会保证输出答案只有唯一解。
输入
第一行输入一个数字 N,表示相册的个数(0<N<10),接下来输入 N 行
每行的输入为 2M 个数字(0<M<100),表示 M 个图片 id 时间戳 键值对的排列。
输出
输出一个以图片 id 重复次数为键值对的数列,按照照片 id 对应的时间戳升序排列。
样例 1
输入:
4
999 1 998 2 997 3 996 4 995 5
994 6 993 7 992 8 991 9 990 10
989 11 988 12 987 13
999 1 995 5 986 14
输出:
999 2 995 2
解释:
id 为 999的照片在所有相册间出现了 2次,记为 999 的照片在所有相册间出现了 2 次
id为999 的照片时间戳为1,id 为 995 的照片时间戳为2
所以按照 999 2 995 2 的顺序输出
样例 2
输入:
3
526 1 564 2 479 4 587 6 357 9
564 2 479 4 587 6 357 9 173 10
526 1 479 4 168 11
输出:
526 2 564 2 479 3 587 2 357 2
解释:
id 为 526 的照片时间戳为 1,id 为 564 的照片时间戳为 2,id 为 479 的照片时间戳为 4,id 为 587 的照片时间戳为 6,id 为 357 的照片时间戳为 9
id为 526 的照片在所有相册间出现了2 次,id 为 564 的照片在所有相册间出现了 2次,id 为 479 的照片在所有相册间出现了 3 次,id 为 587 的照片在所有相册间出现了 2 次,id 为 357 的照片在所有相册间出现了 2 次。
所以输出按照 526 2 564 2 479 3 587 2 357 2的顺序输出