OD C卷【热点网站统计】

题目

企业路由器的统计页面，有一个功能需要动态统计公司访问最多的网页URL top N，设计一个算法，可以高效动态统计TopN的页面；
输入描述：
每一行都是一个url 或者 一个数字；
如果是url，代表一段时间内的网页访问，如果是一个数字N，代表本次需要输出的TopN个url;
输入约束：
总访问网页数量小于5000个，单网页访问次数小于65535次；
网页url仅由字母、数字、点组成，且长度小于等于127字节；
数字是正整数，小于等于10且小于当前总访问网页数；
输出描述：
每个数字输入对应一行输出，输出按访问次数排序TopN个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

解题代码

from functools import cmp_to_key


def cmp(a, b):
    if a[1] != b[1]:
        return b[1] - a[1]  # 降序
    elif a[0] != b[0]:
        return 1 if a[0] > b[0] else -1 # 升序
    else:
        return 0


urls = []
url_map = {}
def statistic(input_str):
    global urls
    global url_map
    n = int(input_str)  # top N
    j = 0
    while j < len(urls):
        if urls[j] not in url_map:
            url_map[urls[j]] = 1
        else:
            url_map[urls[j]] += 1
        j += 1

    url_count = sorted(list(url_map.items()), key=cmp_to_key(cmp), reverse=False)
    output_str = ""
    # 输出字符串
    for i in range(n):
        output_str += url_count[i][0] + ","
    return output_str[:-1]



result = ""
while True:
    try:
        # 输入
        input_str = input().strip()
        if input_str.isdigit():
            # 统计topN
            result+= statistic(input_str) + "\n"
            urls = []
        else:
            # 输入url地址，存入
            urls.append(input_str)
    except:  # 输入结束
        break

print(result[:-1])