题目
企业路由器的统计页面,有一个功能需要动态的统计公司访问最多的网页URL top N。
- 输入描述:每一行都是一个URL或一个数字,如果是URL,代表一段时间内的网页访问;如果是一个数字N,代表本次需要输出的Top N个URL。
输入约束:
1、总访问网页数量小于5000个,单网页访问次数小于65535次;
2、网页URL仅由字母,数字和点分隔符组成,且长度小于等于127字节;
3、数字是正整数,小于等于10且小于当期总访问网页数。
- 输出描述:每行输入要对应一行输出,输出按访问次数排序的前N个URL,用逗号分隔。
输出要求:
1、每次输出要统计之前所有输入,不仅是本次输入;
2、如果访问次数相等的URL,按URL的字符串字典序升序排列,输出排序靠前的URL。
- 示例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
题解
思路:
- 创建2个字典,all_urls用于保存所有URL地址的访问量,tops用于维护top N个URL地址的访问量。其中,all_urls中元素会无限增多,仅做新增和更新、不做排序或循环遍历。
- 1个全局变量min_url,标识tops字典中排在最后个的元素,用于新增URL时做比较是否存入tops中
- tops字典(top N)元素的更新逻辑:
- topN为空
- url在topN中,刷新访问量,重新计算min_url
- url不在topN中、且topN长度小于N,保存至topN中,重新计算min_url
- url不在topN中、且topN长度超过N,临时保存至topN中、再对min_url做删除,最后重新计算min_url
all_urls = {} # 存放所有URL的访问量(不做排序)
tops = {} # 存在topN URL的访问量
min_url = ''
top_num = 10
def save_url(url):
"""
保存URL地址出现的次数,并同步刷新topN的URL。topN只维护前N个URL地址
"""
global min_url
if url in all_urls:
all_urls[url] += 1
else:
all_urls[url] = 1
# 1.topN为空,确定min_url的值
if len(tops) == 0:
tops[url] = 1
min_url = url
# 2.url在topN中,刷新访问量,重新计算min_url
elif url in tops:
tops[url] += 1
min_url = compare_url(min_url, url)
# 3.url不在topN中、且topN长度小于N,保存至topN中,重新计算min_url
elif url not in tops and len(tops) < top_num:
tops[url] = all_urls[url]
min_url = compare_url(min_url, url)
# 4.url不在topN中、且topN长度超过N,临时保存至topN中、再对min_url做删除,最后重新计算min_url
else:
tops[url] = all_urls[url]
temp = sort_top_url()
tops.pop(temp[-1]) # 先存入,进行排序后删除value值最小或key字典序最大的
min_url = temp[-2]
def compare_url(url1, url2):
"""
用于简单比较2个URL地址的排序
"""
if all_urls[url1] > all_urls[url2]:
return url2
elif all_urls[url1] < all_urls[url2]:
return url1
elif url1 > url2:
return url2
elif url1 < url2 or url1 == url2:
return url1
def sort_top_url():
"""
对topN字典进行排序,返回URL列表。排序规则:key不同,根据value值降序排序;key相同,根据key字典序升序排序
"""
temp = sorted(tops.items(), key=lambda kv: (-kv[1], kv[0]))
return [key[0] for key in temp]
def get_top_url(num):
"""
获取前num个URL地址
"""
urls = sort_top_url()
return urls[0:int(num)]
if __name__ == "__main__":
while True:
n = input()
if n.isdigit():
print(",".join(get_top_url(n)))
else:
save_url(n)