E卷-刷题笔记合集🔗

热点网站统计

问题描述

企业路由器的统计页面有一个功能，需要动态统计公司访问最多的网页 URL 的 top N。请设计一个算法，可以高效动态统计 Top N 的页面。

输入格式

输入包含多行，每一行可能是以下两种情况之一：

1. 一个 URL 字符串，表示一段时间内的网页访问。
2. 一个正整数 ，表示本次需要输出的 Top N 个 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

样例输出1

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

样例输出2

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

样例解释

数据范围

• 总访问网页数量小于 5000 个。
• 单网页访问次数小于 65535 次。
• 网页 URL 仅由字母、数字和点分隔符组成，且长度小于等于 127 字节。
• 输入的数字 是正整数，小于等于 10 且小于当前总访问网页数。

题解

模拟+哈希表

这道题目要求我们实现一个动态统计系统，能够记录网页 URL 的访问次数，并随时输出访问次数最多的 Top N 个 URL。

解题思路如下：

1. 使用哈希表（字典）记录每个 URL 的访问次数。这样可以在 O(1) 的时间复杂度内更新和查询访问次数。
2. 维护一个按访问次数排序的列表，存储所有 URL。每次更新 URL 访问次数时，也要更新这个排序列表。
3. 当需要输出 Top N 时，直接从排序列表的前 N 个元素中获取结果。
4. 注意处理访问次数相同时按 URL 字典序排序的要求。

时间复杂度分析：

• 更新 URL 访问次数：O(log m)，其中 m 是不同 URL 的数量
• 输出 Top N：O(N log N)

参考代码

• Python

from collections import defaultdict

class URLTracker:
    def __init__(self):
        self.url_count = defaultdict(int)  # 记录每个URL的访问次数
        self.sorted_urls = []  # 按访问次数排序的URL列表

    def visit(self, url):
        self.url_count[url] += 1  # 增加URL的访问次数
        count = self.url_count[url]
        
        # 更新排序列表
        if url in self.sorted_urls:
            self.sorted_urls.remove(url)
        
        # 找到插入位置并插入
        insert_pos = len(self.sorted_urls)
        for i, u in enumerate(self.sorted_urls):
            if self.url_count[u] < count or (self.url_count[u] == count and u > url):
                insert_pos = i
                break
        self.sorted_urls.insert(insert_pos, url)

    def top_n(self, n):
        return ','.join(self.sorted_urls[:n])

def main():
    tracker = URLTracker()
    while True:
        try:
            line = input().strip()
            if line.isdigit():
                print(tracker.top_n(int(line)))
            else:
                tracker.visit(line)
        except EOFError:
            break

if __name__ == "__main__":
    main()

• C

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

#define MAX_URL 5000
#define MAX_LENGTH 128

typedef struct {
    char url[MAX_LENGTH];
    int count;
} URLCount;

URLCount urls[MAX_URL];
int url_count = 0;

// 比较函数，用于qsort
int compare(const void* a, const void* b) {
    URLCount* ua = (URLCount*)a;
    URLCount* ub = (URLCount*)b;
    if (ua->count != ub->count)
        return ub->count - ua->count;  // 降序排列
    return strcmp(ua->url, ub->url);   // 字典序升序
}

void visit_url(const char* url) {
    int i;
    for (i = 0; i < url_count; i++) {
        if (strcmp(urls[i].url, url) == 0) {
            urls[i].count++;
            qsort(urls, url_count, sizeof(URLCount), compare);
            return;
        }
    }
    if (url_count < MAX_URL) {
        strcpy(urls[url_count].url, url);
        urls[url_count].count = 1;
        url_count++;
        qsort(urls, url_count, sizeof(URLCount), compare);
    }
}

void print_top_n(int n) {
    for (int i = 0; i < n && i < url_count; i++) {
        printf("%s%s", i > 0 ? "," : "", urls[i].url);
    }
    printf("\n");
}

int main() {
    char input[MAX_LENGTH];
    while (scanf("%s", input) != EOF) {
        if (input[0] >= '0' && input[0] <= '9') {
            print_top_n(atoi(input));
        } else {
            visit_url(input);
        }
    }
    return 0;
}

• Javascript

const readline = require('readline');

class URLTracker {
    constructor() {
        this.urlCount = new Map();
        this.sortedUrls = [];
    }

    visit(url) {
        const count = (this.urlCount.get(url) || 0) + 1;
        this.urlCount.set(url, count);

        // 更新排序列表
        const index = this.sortedUrls.indexOf(url);
        if (index !== -1) {
            this.sortedUrls.splice(index, 1);
        }

        // 找到插入位置并插入
        let insertPos = this.sortedUrls.length;
        for (let i = 0; i < this.sortedUrls.length; i++) {
            const u = this.sortedUrls[i];
            if (this.urlCount.get(u) < count || (this.urlCount.get(u) === count && u > url)) {
                insertPos = i;
                break;
            }
        }
        this.sortedUrls.splice(insertPos, 0, url);
    }

    topN(n) {
        return this.sortedUrls.slice(0, n).join(',');
    }
}

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const tracker = new URLTracker();

rl.on('line', (line) => {
    if (/^\d+$/.test(line)) {
        console.log(tracker.topN(parseInt(line)));
    } else {
        tracker.visit(line);
    }
});

rl.on('close', () => {
    process.exit(0);
});

• Java

import java.util.*;

public class Main {
    static class URLTracker {
        private Map<String, Integer> urlCount = new HashMap<>();
        private List<String> sortedUrls = new ArrayList<>();

        public void visit(String url) {
            int count = urlCount.getOrDefault(url, 0) + 1;
            urlCount.put(url, count);

            // 更新排序列表
            sortedUrls.remove(url);

            // 找到插入位置并插入
            int insertPos = sortedUrls.size();
            for (int i = 0; i < sortedUrls.size(); i++) {
                String u = sortedUrls.get(i);
                if (urlCount.get(u) < count || (urlCount.get(u).equals(count) && u.compareTo(url) > 0)) {
                    insertPos = i;
                    break;
                }
            }
            sortedUrls.add(insertPos, url);
        }

        public String topN(int n) {
            return String.join(",", sortedUrls.subList(0, Math.min(n, sortedUrls.size())));
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        URLTracker tracker = new URLTracker();

        while (scanner.hasNext()) {
            String input = scanner.next();
            if (input.matches("\\d+")) {
                System.out.println(tracker.topN(Integer.parseInt(input)));
            } else {
                tracker.visit(input);
            }
        }

        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

class URLTracker {
private:
    unordered_map<string, int> urlCount;
    vector<string> sortedUrls;

public:
    void visit(const string& url) {
        int count = ++urlCount[url];

        // 更新排序列表
        auto it = find(sortedUrls.begin(), sortedUrls.end(), url);
        if (it != sortedUrls.end()) {
            sortedUrls.erase(it);
        }

        // 找到插入位置并插入
        auto insertPos = sortedUrls.end();
        for (auto it = sortedUrls.begin(); it != sortedUrls.end(); ++it) {
            if (urlCount[*it] < count || (urlCount[*it] == count && *it > url)) {
                insertPos = it;
                break;
            }
        }
        sortedUrls.insert(insertPos, url);
    }

    string topN(int n) {
        string result;
        for (int i = 0; i < n && i < sortedUrls.size(); ++i) {
            if (i > 0) result += ",";
            result += sortedUrls[i];
        }
        return result;
    }
};

int main() {
    URLTracker tracker;
    string input;

    while (cin >> input) {
        if (isdigit(input[0])) {
            cout << tracker.topN(stoi(input)) << endl;
        } else {
            tracker.visit(input);
        }
    }

    return 0;
}