题目描述

公司有一个路由器统计页面，要求动态统计公司内访问量最多的 URL 的 Top N。输入由 URL 和数字 N 组成，URL 表示访问的网页，数字 N 表示需要输出访问次数最高的 Top N 个 URL，输出按照访问次数降序排列，如果访问次数相同，则按字典序升序排列。

输入描述

• 每一行输入是一个 URL 或一个正整数 N。
• 如果是 URL，表示网页访问记录；如果是 N，表示当前要输出的 Top N 个 URL。
• 输入约束：
  • 总访问网页数小于 5000 个，单个网页访问次数小于 65535 次；
  • 网页 URL 仅由字母、数字和 . 组成，长度不超过 127 字节；
  • 数字 N 小于等于 10，且小于当前总访问网页数。

输出描述

• 每次输出按之前所有输入统计的 Top N 访问量最高的 URL，用逗号分隔。
• 如果有多个 URL 访问次数相同，按字典序升序排列。

题解思路

1. 数据结构：使用 unordered_map 来存储 URL 的访问次数。
2. 优先队列：用自定义结构体 URLRecord 和 priority_queue 获取访问次数最高的 N 个 URL。priority_queue 结合自定义比较规则，使 URL 按访问次数降序排列，若访问次数相同则按字典序升序排列。
3. 处理输入：
   • 若输入为 URL，更新其在 unordered_map 中的访问次数。
   • 若输入为数字 N，使用优先队列对所有 URL 统计访问次数，并提取前 N 个结果输出。

复杂度分析

• 时间复杂度：处理每个 URL 插入到 unordered_map 为 O(1)，每次查询 Top N 需要遍历 unordered_map 并插入 priority_queue，因此为 O(M log M)（其中 M 为 unordered_map 中的元素数量）。
• 空间复杂度：优先队列和哈希表的空间总复杂度为 O(M)。

代码实现

C++

#include <bits/stdc++.h>
using namespace std;

// 自定义结构，用于在优先队列中存储URL和访问次数
struct URLRecord {
    string url;
    int count;

    // 自定义比较规则
    bool operator<(const URLRecord& other) const {
        if (count == other.count) {
            return url > other.url; // 访问次数相同按字典序升序排列
        }
        return count < other.count; // 访问次数降序排列
    }
};

// 统计访问次数的哈希表
unordered_map<string, int> urlCount;

void processInput(const string& input) {
    // 判断输入是否为数字
    if (isdigit(input[0])) {
        int N = stoi(input);
        
        // 使用优先队列获取前N个访问次数最多的URL
        priority_queue<URLRecord> pq;
        for (const auto& entry : urlCount) {
            pq.push({entry.first, entry.second});
        }

        vector<string> topN;
        for (int i = 0; i < N && !pq.empty(); ++i) {
            topN.push_back(pq.top().url);
            pq.pop();
        }

        // 输出结果
        for (int i = 0; i < topN.size(); ++i) {
            if (i > 0) cout << ",";
            cout << topN[i];
        }
        cout << endl;
    } else {
        // 如果是URL，将其计数增加
        urlCount[input]++;
    }
}

int main() {
    string line;
    while (cin >> line) {
        processInput(line);
    }
    return 0;
}

Python

import heapq
from collections import defaultdict

# 统计访问次数的字典
url_count = defaultdict(int)

def process_input(input_line):
    if input_line.isdigit():
        N = int(input_line)
        
        # 使用堆来获取前N个访问次数最多的URL
        pq = []
        for url, count in url_count.items():
            heapq.heappush(pq, (-count, url))  # 使用负数实现最大堆
        top_n = []
        for _ in range(N):
            top_n.append(heapq.heappop(pq)[1])
        
        print(",".join(top_n))
    else:
        # 如果是URL，将其计数增加
        url_count[input_line] += 1

# 模拟输入
while True:
    try:
        line = input().strip()
        process_input(line)
    except EOFError:
        break

Java

import java.util.*;

public class Main {
    static Map<String, Integer> urlCount = new HashMap<>();

    public static void processInput(String input) {
        if (Character.isDigit(input.charAt(0))) {
            int N = Integer.parseInt(input);
            
            // 使用优先队列获取前N个访问次数最多的URL
            PriorityQueue<URLRecord> pq = new PriorityQueue<>();
            for (Map.Entry<String, Integer> entry : urlCount.entrySet()) {
                pq.add(new URLRecord(entry.getKey(), entry.getValue()));
            }

            List<String> topN = new ArrayList<>();
            int cnt = N;
            while (cnt > 0 && !pq.isEmpty()) {
                topN.add(pq.poll().url);
                cnt --;
            }
            System.out.println(String.join(",", topN));
        } else {
            // 如果是URL，将其计数增加
            urlCount.put(input, urlCount.getOrDefault(input, 0) + 1);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String line = scanner.nextLine().trim();
            processInput(line);
        }
    }
}

class URLRecord implements Comparable<URLRecord> {
    String url;
    int count;

    public URLRecord(String url, int count) {
        this.url = url;
        this.count = count;
    }

    @Override
    public int compareTo(URLRecord other) {
        if (this.count == other.count) {
            return this.url.compareTo(other.url); // 访问次数相同按字典序升序排列
        }
        return Integer.compare(other.count, this.count); // 访问次数降序排列
    }
}

题目描述

企业路由器的统计页面，有一个功能需要动态统计公司访问最多的网页 $URL$ $top$ $N$ 。

请设计一个算法，可以高效动态统计 $Top$ $N$的页面。

输入描述

每一行都是一个 $URL$ 或一个数字，如果是 $URL$ ，代表一段时间内的网页访问； 如果是一个数字 $N$ ，代表本次需要输出的$Top$ $N$个 $URL$。

输入约束：

1、总访问网页数量小于 $5000$ 个，单网页访问次数小于 $65535$ 次；

2、网页 $URL$ 仅由字母，数字和点分隔符组成，且长度小于等于 $127$ 字节；

3、数字是正整数，小于等于 $10$ 且小于当前总访问网页数；

输出描述

每行输入要对应一行输出，输出按访问次数排序的前 $N$ 个 $URL$ ，用逗号分隔。

输出要求：

1、每次输出要统计之前所有输入，不仅是本次输入；

2、如果有访问次数相等的 $URL$ ，按 $URL$ 的字符串字典序升序排列，输出排序靠前的 $URL$ ；

样例1

输入

news.qq.com
news.sina.com.cn
news.qq.com
news.qq.com
game.163.com
game.163.com
www.huawei.com
www.cctv.com
3
www.huawei.com
www.cctv.com
www.huawei.com
www.cctv.com
www.huawei.com
www.cctv.com
www.huawei.com
www.cctv.com
www.huawei.com
3

输出

news.qq.com,game.163.com,news.sina.com.cn
www.huawei.com,www.cctv.com,news.qq.com

样例2

输入

news.qq.com
www.cctv.com
1
www.huawei.com
www.huawei.com
2
3

输出

news.qq.com
www.huawei.com,news.qq.com
www.huawei.com,news.qq.com,www.cctv.com