字符串出现次数的TopK问题

题目:给定一个字符串数组,再给定整数k,请返回出现次数前k名的字符串和对应的次数。返回的答案应该按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率,按字典序排序。字符仅包含数字和字母

对于两个字符串,大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系。比如"ah1x"小于"ahb","231"<”32“

例子:

输入:
["123","123","231","32"],2
复制
返回值:
[["123","2"],["231","1"]]
复制
说明:
 "123"出现了2次,记["123","2"],"231"与"32"各出现1次,但是"231"字典序在"32"前面,记["231","1"],最后返回[["123","2"],["231","1"]] 

分析:

  • 难点是词频相同时,词频高的排前面;词频不同时,字符字典序低的排前面

  • 用哈希表记录字符,其出现的次数;定义一个Node接受字符str和它对应的词频

    • Node implements Comparable<Node>重写compareTo

    • // 排序逻辑:排序在前面的,返回负数,排序在后面的,返回正数
      // 1.词频相同,词频高的在前,返回负数
      // 2.词频不相同,字典序低的在前,返回负数
      @Override
      public int compareTo(Node node) {
          if (this.times == node.times) {// 词频一样,比较字符串
              return this.str.compareTo(node.str);
          } else {// 词频不一样,就比较词频
              return node.times - this.times;
          }
      }
  • 生成k个长度的小根堆(排前面的CompareTo返回正数,排后面的CompareTo返回负数),来接受遍历到的strs中的字符串

    • 堆未满,就一直加入
    • 堆满了,堆满了,如果小根堆顶应该排在待插入元素的后面(>0),就更新堆顶
    • heapifyheapInsert自行看代码
  • 重新调整小根堆,使排序在前的放在堆顶

  • 结果集接受堆中数据,返回结果集

public class Solution {

    public static class Node implements Comparable<Node> {
        public String str;
        public int times;

        public Node(String str, int times) {
            this.str = str;
            this.times = times;
        }

        // 排序逻辑:排序在前面的,返回负数,排序在后面的,返回正数
        // 1.词频相同,词频高的在前,返回负数
        // 2.词频不相同,字典序低的在前,返回负数
        @Override
        public int compareTo(Node node) {
            if (this.times == node.times) {// 词频一样,比较字符串
                return this.str.compareTo(node.str);
            } else {// 词频不一样,就比较词频
                return node.times - this.times;
            }
        }
    }

    public String[][] topKstrings(String[] strings, int k) {
        if (strings == null || k < 1) {
            return new String[][]{};
        }
        // map统计每个字符,出现的词频
        HashMap<String, Integer> map = new HashMap<>();
        for (String s : strings) {
            if (!map.containsKey(s)) {
                map.put(s, 1);
            } else if (map.containsKey(s)) {
                map.put(s, map.get(s) + 1);
            }
        }
        // 遍历哈希表,每个node放入小根堆中
        // minHeap中的"小"指的是:排序放在后面的放在堆顶(compareTo返回正数)
        Node[] minHeap = new Node[k];
        int index = 0;
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String str = entry.getKey();
            Integer times = entry.getValue();
            Node node = new Node(str, times);
            if (index < k) {// 堆未满,就加入
                minHeap[index] = node;
                heapInsert(minHeap, index++);
            } else {
                if (minHeap[0].compareTo(node) > 0) {// 堆满了,如果小根堆顶应该排在待插入元素的后面(>0),就更新堆顶
                    minHeap[0] = node;
                    heapify(minHeap, 0, k);
                }
            }
        }
        // 重新调整小根堆,使排序在前的放在堆顶
        for (int i = index - 1; i >= 0; i--) {
            swap(minHeap, 0, i);
            heapify(minHeap, 0, i);
        }
        // 结果集接受堆中数据,返回结果集
        String[][] res = new String[k][2];
        for (int i = 0; i < k; i++) {
            // 小根堆,就倒序放入res中
            res[i][0] = minHeap[i].str;
            res[i][1] = String.valueOf(minHeap[i].times);
        }
        return res;
    }

    private void heapify(Node[] minHeap, int index, int size) {
        while (2 * index + 1 < size) {
            int left = 2 * index + 1;
            // 越排在后面的,compareTo返回的越大,找出左右孩子节点中的排序后在更后面的
            if (left + 1 < size && minHeap[left].compareTo(minHeap[left + 1]) < 0) {
                left++;
            }
            // 如果父亲已经比孩子中最靠后的还要排序在后面,就停止本轮循环
            if (minHeap[index].compareTo(minHeap[left]) > 0) {
                break;
            }
            swap(minHeap, index, left);
            index = left;
        }
    }

    // 小根堆未满,加入堆时,排序小的往上放
    private void heapInsert(Node[] heap, int index) {
        while (index != 0) {
            int parent = (index - 1) / 2;
            // 返回正数,应该放后面,所以交换
            if (heap[index].compareTo(heap[parent]) > 0) {
                swap(heap, parent, index);
                index = parent;
            } else {
                break;
            }
        }
    }

    private void swap(Node[] minHeap, int i, int j) {
        Node temp = minHeap[i];
        minHeap[i] = minHeap[j];
        minHeap[j] = temp;
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] strs = {"abcd", "abcd", "abcd", "pwb2", "abcd", "pwb2", "p12"};
        int k = 3;
        String[][] res = solution.topKstrings(strs, k);
        // 正确:[["abcd","4"],["pwb2","2"],["p12","1"]]
        System.out.println(Arrays.deepToString(res));
        System.out.println("---------");
        String s1 = "231";
        String s2 = "32";
        Node n1 = new Node(s1, 1);// 词频相同,231字典序<32,返回负数
        Node n2 = new Node(s2, 1);

        Node n3 = new Node(s1, 1);// 词频不相同,231词频<32词频,返回正数
        Node n4 = new Node(s2, 2);

        System.out.println(n1.compareTo(n2));// -1
        System.out.println(n3.compareTo(n4));// 1

    }
}