题目链接

小苯的文章浏览

题目描述

小苯收到 条文章浏览记录，每条记录都是一个用户的 ID 字符串。同一个用户可能会浏览多次，产生多条记录。

需要按照这些记录的出现顺序，输出所有独立用户的 ID，每个 ID 只输出其第一次出现的那一次。

解题思路

这个问题要求我们对一个数据流进行去重，同时保持每个元素首次出现的相对顺序。这是一个经典的“首次出现”或“顺序去重”问题。

解决这个问题的关键在于，当我们处理每条浏览记录时，需要能快速判断“这个用户 ID 之前是否已经出现过？”。

哈希集合（Hash Set） 是解决此类问题的理想数据结构。它可以在平均 的时间内完成插入和查找操作。

具体的算法步骤如下：

  1. 创建一个空的哈希集合，例如 seen_users，用来存放所有已经遇到过的、独一无二的用户 ID。

  2. 读取总的记录条数 。

  3. 循环 次，按顺序处理每一条浏览记录：

    a. 读取当前的用户 ID 字符串 current_id。

    b. 检查 seen_users 集合中是否已经包含 current_id。

    c. 如果不包含，说明这是该用户第一次浏览。此时，我们应该： i. 将 current_id 输出。 ii. 将 current_id 添加到 seen_users 集合中，以记录我们已经处理过这个用户。

    d. 如果包含，说明这个用户之前已经浏览过，我们直接忽略这条记录，继续处理下一条。

  4. 循环结束后，所有首次浏览的用户 ID 就已经按顺序输出完毕了。

根据用户的偏好，在 C++ 中我们将使用 std::set 来实现。

代码

#include <iostream>
#include <string>
#include <set>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    set<string> seen_users;
    for (int i = 0; i < n; ++i) {
        string user_id;
        cin >> user_id;
        
        // set::count() 返回 0 或 1
        if (seen_users.count(user_id) == 0) {
            cout << user_id << "\n";
            seen_users.insert(user_id);
        }
    }

    return 0;
}

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        Set<String> seenUsers = new HashSet<>();
        
        for (int i = 0; i < n; i++) {
            String userId = sc.next();
            if (!seenUsers.contains(userId)) {
                System.out.println(userId);
                seenUsers.add(userId);
            }
        }
    }
}

import sys

def solve():
    try:
        n_str = sys.stdin.readline().strip()
        if not n_str: return
        n = int(n_str)
        
        seen_users = set()
        for _ in range(n):
            user_id = sys.stdin.readline().strip()
            if user_id not in seen_users:
                print(user_id)
                seen_users.add(user_id)
                
    except (IOError, ValueError):
        return

solve()

算法及复杂度

  • 算法：模拟 + 哈希集合

  • 时间复杂度：令 为浏览记录的总条数， 为用户 ID 的平均长度。

    • 对于哈希集合（HashSet, Python set），每次插入和查找的平均时间复杂度是 （字符串哈希和比较所需的时间）。总时间复杂度为 。
    • 对于基于平衡树的集合（C++ std::set），每次操作的复杂度是 ，其中 是当前集合中唯一用户的数量。总时间复杂度为 。

  • 空间复杂度：，其中 是独立用户的总数。我们需要存储所有不重复的用户 ID。