一、简介

给定一个字符串数组，再给定整数 k ，请返回出现次数前k名的字符串和对应的次数。

返回的答案应该按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率，按字典序排序。

对于两个字符串，大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系。

比如"ah1x"小于"ahb"，"231"<”32“

字符仅包含数字和字母

输入：
["a","b","c","b"],2
返回值：
[["b","2"],["a","1"]]
说明：
"b"出现了2次，记["b","2"]，"a"与"c"各出现1次，但是a字典序在c前面，记["a","1"]，最后返回[["b","2"],["a","1"]]

二、实现

思路1：先使用hash计算出每个字符串出现的次数，然后将hash转为数组，进行排序，最后输出k个数字即可

type MapNode struct {
    str string
    times int
}
/**
 * return topK string
 * @param strings string字符串一维数组 strings
 * @param k int整型 the k
 * @return string字符串二维数组
*/
func topKstrings( strings []string ,  k int ) [][]string {
    // write code here
    if len(strings) == 0 {
        return nil
    }
    
    dataMap := make(map[string]int) // 用于统计每个字符串出现次数
    for _,item := range strings {
       dataMap[item] = dataMap[item] + 1
    }
    
    dataList := make([]MapNode, 0) // 为了排序方便，转为数组
    for k,v := range dataMap {
        dataList = append(dataList, MapNode{
            str:k,
            times:v,
        })
    }
    
    // 排序数组
    sort.Slice(dataList, func(i, j int) bool {
        if dataList[i].times == dataList[j].times {
            return dataList[i].str > dataList[j].str
        }
        
        return  dataList[i].times < dataList[j].times
	})
    
    // 输出倒数k个
    rs := make([][]string, 0)
    var i = len(dataList) -1
    for i >= 0 && k > 0{
        rs = append(rs, []string{
            dataList[i].str,
            fmt.Sprint(dataList[i].times),
        })
        
        i--
        k --
    }
    
    return rs
}

思路2：先使用hash计算出每个字符串出现的次数，然后以k个最大数构建最小堆，最后利用堆排序

/**
 * return topK string
 * @param strings string字符串一维数组 strings
 * @param k int整型 the k
 * @return string字符串二维数组
 */
func topKstrings(strings []string, k int) [][]string {
   // write code here
   dataMap := make(map[string]int)
   for _, item := range strings {
      dataMap[item] = dataMap[item] + 1
   }

   // 以最大的k个数，构建最小堆
   strList := make([]string, 0)
   for str := range dataMap {
      if len(strList) < k {
         strList = append(strList, str)
         if len(strList) == k {
            // 构建最小堆
            index := len(strList)/2 - 1
            for index >= 0 {
               jumpHeap(index, strList, dataMap)

               index--
            }
         }

         continue
      } else if comp(str, strList[0], dataMap) {
         continue
      } else {
         strList[0] = str
         jumpHeap(0, strList, dataMap)
      }
   }

   // 将heap中的元素进行排序
   rs := make([][]string, k)
   for i := 0; i < k; i++ {
      if len(strList) == 0 {
         break
      }

      rs[k - i -1] = []string{
         strList[0],
         fmt.Sprint(dataMap[strList[0]]),
      }

      strList = strList[1:]

      // 再次构建堆
      index := len(strList)/2 - 1
      for index >= 0 {
         jumpHeap(index, strList, dataMap)

         index--
      }
   }

   return rs
}

func jumpHeap(index int, data []string, dataMap map[string]int) {
   // 构建堆
   leftIndex := 2*index + 1
   rightIndex := 2*index + 2

   if leftIndex >= len(data) {
      return
   }

   if rightIndex >= len(data) {
      if comp(data[index], data[leftIndex], dataMap) {
         return
      }

      data[index], data[leftIndex] = data[leftIndex], data[index]

      jumpHeap(leftIndex, data, dataMap)
      return
   }

   // 根节点为最小值
   if comp(data[index], data[leftIndex], dataMap) && comp(data[index], data[rightIndex], dataMap) {
      return
   }

   // 左节点为最小值
   if comp(data[leftIndex], data[index], dataMap) && comp(data[leftIndex], data[rightIndex], dataMap) {
      data[index], data[leftIndex] = data[leftIndex], data[index]

      jumpHeap(leftIndex, data, dataMap)
      return
   }

   // 右节点为最小值
   data[index], data[rightIndex] = data[rightIndex], data[index]

   jumpHeap(rightIndex, data, dataMap)
   return
}

// 判断str1 是否小于 str2
func comp(str1, str2 string, dataMap map[string]int) bool {
   if dataMap[str2] == dataMap[str1] {
      return str1 <= str2
   }

   return dataMap[str1] <= dataMap[str2]
}

题目来源：牛客