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

示例二

输入

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

解题思路

显然是考察排序的一道题目。

每一行的输入只会是两种情况

输入URL，表示某一网站访问过
输入数字N，表示需要返回访问次数Top N的那些网站，并且对它们进行排序

注意到每次输入URL的时候，都需要重新更新它的访问次数，这很明显可以使用哈希表来完成关于访问次数的统计。此外，由于输入的长度不定，因此需要使用try-except异常处理语句来进行编写输入。

因此整体的代码框架如下

cnt = Counter()
ans = list()

while 1:
    try:
        item = input()
        if item.isdigit():
            pass
        else:
            cnt[item] += 1
    except:
        break

剩下的内容就是要处理代码中，关于输入之后的排序部分。

注意到我们首先要根据出现频次降序排列，相同频次的再按照字典序升序排列。

排序的对象为cnt中的这些key（若干的URL）组成的列表，故对应的lambda函数为

sorted(cnt.keys(), key = lambda x: (-cnt[x], x))

如果再加上取前N个的切片操作，以及用","进行合并为字符串，再将字符串存入ans中，则代码为

N = int(item)
temp = sorted(cnt.keys(), key = lambda x: (-cnt[x], x))
ans.append(",".join(temp[:N]))

把上述代码放入上述代码框架中的pass部分，就基本完成了本题。

代码

Python

# 题目：【排序】热点网站统计
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：模拟，排序，哈希表
# 代码看不懂的地方，请直接在群上提问

from collections import Counter

# 构建哈希表cnt，储存每一个URL的访问次数
cnt = Counter()
# 构建ans储存最终每一次输出结果
ans = list()

# 输入行数不确定，使用while加上try-except语句进行处理
while 1:
    try:
        item = input()
        # 如果输入的是数字，则需要进行输出
        if item.isdigit():
            N = int(item)
            # 排序对象是cnt中的所有key（所有URL）
            # 先根据-cnt[x]进行URL出现频率的降序排序，再根据字典序进行排序
            temp = sorted(cnt.keys(), key=lambda x: (-cnt[x], x))
            # 使用切片取前N个元素，用逗号合并后储存在ans中
            ans.append(",".join(temp[:N]))
        else:
            cnt[item] += 1
    except:
        break

# 输出ans中的每一行
for row in ans:
    print(row)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Map<String, Integer> cnt = new HashMap<>(); // 哈希表，存储每个URL及其访问次数
        List<String> ans = new ArrayList<>();       // 存储最终的每一次输出结果
        
        while (scanner.hasNextLine()) {             // 不确定行数，逐行读取输入
            String input = scanner.nextLine();
            if (input.matches("\\d+")) {            // 如果输入的是数字，进行输出处理
                int N = Integer.parseInt(input);    // 转换为整数
                List<Map.Entry<String, Integer>> sortedCnt = new ArrayList<>(cnt.entrySet());
                
                // 使用自定义排序规则排序
                sortedCnt.sort((a, b) -> {
                    if (!a.getValue().equals(b.getValue())) {
                        return b.getValue() - a.getValue(); // 按访问次数降序
                    }
                    return a.getKey().compareTo(b.getKey()); // 按字典序升序
                });
                
                StringBuilder result = new StringBuilder();
                for (int i = 0; i < N && i < sortedCnt.size(); i++) {    // 获取前N个URL
                    if (i > 0) result.append(",");                       // 逗号分隔
                    result.append(sortedCnt.get(i).getKey());
                }
                ans.add(result.toString());  // 将结果存入ans列表中
            } else {                         // 如果输入的是URL，则更新哈希表
                cnt.put(input, cnt.getOrDefault(input, 0) + 1);
            }
        }
        for (String row : ans) {             // 输出结果
            System.out.println(row);
        }
    }
}

C++

#include <iostream>
#include <string>
#include <unordered_map>
#include <map>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;

// 自定义排序函数，根据访问次数降序排序，若次数相同按字典序排序
bool compare(pair<string, int>& a, pair<string, int>& b) {
    if (a.second != b.second)
        return a.second > b.second; // 先按访问次数降序排序
    return a.first < b.first;       // 再按字典序排序
}

int main() {
    unordered_map<string, int> cnt; // 哈希表，存储每个URL及其访问次数
    vector<string> ans;             // 存储最终的每一次输出结果
    string input;                   // 用于存储输入的行
    while (getline(cin, input)) {   // 不确定行数，使用getline逐行读取输入
        if (isdigit(input[0])) {    // 如果输入的是数字，进行输出处理
            int N = stoi(input);    // 转换为整数
            vector<pair<string, int>> sortedCnt(cnt.begin(), cnt.end()); // 转换为可排序的向量
            sort(sortedCnt.begin(), sortedCnt.end(), compare);           // 使用自定义排序规则排序
            stringstream result;
            for (int i = 0; i < N && i < sortedCnt.size(); i++) {        // 获取前N个URL
                if (i > 0) result << ",";                                // 逗号分隔
                result << sortedCnt[i].first;
            }
            ans.push_back(result.str()); // 将结果存入ans向量中
        } else {                         // 如果输入的是URL，则更新哈希表
            cnt[input]++;
        }
    }
    for (const string& row : ans) {      // 输出结果
        cout << row << endl;
    }
    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

// 定义一个结构体用于存储URL及其访问次数
typedef struct {
    char url[101];  // URL的字符串
    int count;      // URL的访问次数
} URLCount;

// 比较函数，用于按访问次数降序排序，如果访问次数相等则按字典序升序排序
int compare(const void *a, const void *b) {
    URLCount *urlA = (URLCount *)a;
    URLCount *urlB = (URLCount *)b;
    if (urlB->count != urlA->count) {
        return urlB->count - urlA->count;  // 按访问次数降序
    }
    return strcmp(urlA->url, urlB->url);  // 按字典序升序
}

int main() {
    URLCount urlCounts[1000];  // 存储URL及其访问次数
    int urlIndex = 0;          // 当前存储的URL数量
    char input[101];           // 输入的字符串
    char results[100][1001];   // 存储输出结果
    int resultIndex = 0;       // 结果索引

    // 初始化urlCounts数组
    for (int i = 0; i < 1000; i++) {
        urlCounts[i].url[0] = '\0';
        urlCounts[i].count = 0;
    }

    // 持续读取输入，直到遇到EOF
    while (fgets(input, sizeof(input), stdin)) {
        // 去掉输入末尾的换行符
        input[strcspn(input, "\n")] = '\0';

        // 检查是否是数字
        int isNumber = 1;
        for (int i = 0; input[i] != '\0'; i++) {
            if (!isdigit(input[i])) {
                isNumber = 0;
                break;
            }
        }

        if (isNumber) {
            // 如果是数字，转换为整数并进行输出
            int N = atoi(input);

            // 对urlCounts数组进行排序
            qsort(urlCounts, urlIndex, sizeof(URLCount), compare);

            // 拼接前N个URL
            char temp[1001] = "";
            for (int i = 0; i < N && i < urlIndex; i++) {
                if (i > 0) {
                    strcat(temp, ",");
                }
                strcat(temp, urlCounts[i].url);
            }

            // 存储结果
            strcpy(results[resultIndex++], temp);
        } else {
            // 如果是URL，更新访问次数
            int found = 0;
            for (int i = 0; i < urlIndex; i++) {
                if (strcmp(urlCounts[i].url, input) == 0) {
                    urlCounts[i].count++;
                    found = 1;
                    break;
                }
            }
            if (!found) {
                strcpy(urlCounts[urlIndex].url, input);
                urlCounts[urlIndex].count = 1;
                urlIndex++;
            }
        }
    }

    // 输出所有结果
    for (int i = 0; i < resultIndex; i++) {
        printf("%s\n", results[i]);
    }

    return 0;
}

Node JavaScript

// 引入 readline 模块处理输入
const readline = require("readline");

// 创建读取接口
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

// 哈希表，用于储存每个URL及其访问次数
const cnt = new Map();
// 存储最终每一次输出结果
const ans = [];

// 用于读取所有输入
const inputLines = [];

// 处理输入数据
rl.on("line", (line) => {
    inputLines.push(line.trim());
});

// 输入处理结束后，执行逻辑
rl.on("close", () => {
    for (let item of inputLines) {
        // 如果输入的是数字，则需要进行输出
        if (/^\d+$/.test(item)) {
            const N = parseInt(item); // 转换为数字
            // 将cnt哈希表转换为数组，并按规则排序
            const sortedKeys = Array.from(cnt.keys()).sort((a, b) => {
                if (cnt.get(b) !== cnt.get(a)) {
                    return cnt.get(b) - cnt.get(a); // 按访问次数降序
                }
                return a.localeCompare(b); // 按字典序升序
            });
            // 取前N个元素，用逗号合并后加入结果列表
            ans.push(sortedKeys.slice(0, N).join(","));
        } else {
            // 如果输入的是URL，更新哈希表
            cnt.set(item, (cnt.get(item) || 0) + 1);
        }
    }

    // 输出结果
    for (let row of ans) {
        console.log(row);
    }
});

Go

package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
    "strings"
)

// 定义自定义类型用于排序
type urlCount struct {
    url   string
    count int
}

// 自定义排序规则
type byCountAndLex []urlCount

func (a byCountAndLex) Len() int      { return len(a) }
func (a byCountAndLex) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a byCountAndLex) Less(i, j int) bool {
    if a[i].count != a[j].count {
        return a[i].count > a[j].count // 按访问次数降序
    }
    return a[i].url < a[j].url // 按字典序升序
}

func main() {
    // 哈希表，存储每个URL及其访问次数
    cnt := make(map[string]int)
    // 存储最终每一次输出结果
    var ans []string

    scanner := bufio.NewScanner(os.Stdin)
    for scanner.Scan() {
        line := scanner.Text()
        // 如果输入的是数字，则需要进行输出
        if n, err := strconv.Atoi(line); err == nil {
            // 将cnt哈希表转换为切片，并按规则排序
            urls := make([]urlCount, 0, len(cnt))
            for url, count := range cnt {
                urls = append(urls, urlCount{url, count})
            }
            sort.Sort(byCountAndLex(urls))
            // 取前N个元素，用逗号合并后加入结果列表
            var result []string
            for i := 0; i < n && i < len(urls); i++ {
                result = append(result, urls[i].url)
            }
            ans = append(ans, strings.Join(result, ","))
        } else {
            // 如果输入的是URL，更新哈希表
            cnt[line]++
        }
    }

    // 输出结果
    for _, row := range ans {
        fmt.Println(row)
    }
}

时空复杂度

时间复杂度：O(K+TMlogM)。K为输入的URL的条数，M为URL的种类数，T为数字出现的次数。

空间复杂度：O(M)。哈希表所占空间。