热点网站统计

题目描述

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

输入约束

每一行都是一个URL或一个数字，如果是URL代表一段时间内的网页访问，如果是一个数字N 代表本次需要输出的TopN个URL 输入约束:

1. 总访问网页数量小于5000个， 单网页访问次数小于65535次
2. 网页URL仅由字母数字和.分隔符组成，且长度小于等于127字节
3. 数字是正整数，小于等于10 ，且小于当前总访问网页数

输出描述

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

1. 每次输出要统计之前所有输入，不仅是本次输入
2. 如果有访问次数相等的URL，按URL的字符串字典序升序排列，输出排序靠前的URL

输入

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

输出

news.qq.com,game.163.com,news.sina.com.cn
game.163.com,news.qq.com

解题思路

经典TopN问题，求访问次数前N，用最小堆

package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	in := bufio.NewScanner(os.Stdin)
	count := make(map[string]int)
	ans := make([]string, 0)
	h := make(minHeap, 0)
	heap.Init(&h)
	for in.Scan() {
		line := in.Text()
		if len(line) != 1 {
			count[line]++
			continue
		}
		n, _ := strconv.Atoi(line)
		for k, v := range count {
			if h.Len() == n {
				if v < h[0].count && !(v == h[0].count && k < h[0].url) {
					continue
				}
				heap.Pop(&h)
			}
			heap.Push(&h, item{
				url:   k,
				count: v,
			})
		}
		topn := make([]string, n)
		for h.Len() > 0 {
			topn[h.Len()-1] = heap.Pop(&h).(item).url
		}
		ans = append(ans, strings.Join(topn, ","))
	}
	fmt.Println(strings.Join(ans, "\n"))
}

type item struct {
	url   string
	count int
}

type minHeap []item

func (h minHeap) Len() int      { return len(h) }
func (h minHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h minHeap) Less(i, j int) bool {
	return h[i].count < h[j].count
}

func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(item)) }
func (h *minHeap) Pop() interface{} {
	x := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return x
}