【困难】出现次数的TOPK问题－Java：进阶问题

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter

package live.every.day.ProgrammingDesign.CodingInterviewGuide.Other; import java.util.HashMap; /** * 出现次数的TOPK问题 * * 【题目】 * 给定String类型的数组strArr，再给定整数k，请严格按照排名顺序打印出现次数前k名的字符串。 * * 【举例】 * strArr=["1","2","3","4"]，k=2 * No.1: 1, times: 1 * No.2: 2, times: 1 * 这种情况下，所有的字符串都出现一样多，随便打印任何两个字符串都可以。 * * strArr=["1","1","2","3"]，k=2 * 输出： * No.1: 1, times: 2 * No.2: 2, times: 1 * 或者输出： * No.1: 1, times: 2 * No.2: 3, times: 1 * * 【要求】 * 如果strArr长度为N，时间复杂度请达到O(Nlogk)。 * * 【进阶题目】 * 设计并实现TopKRecord结构，可以不断地向其中加入字符串，并且可以根据字符串出现的情况随时打印加入次数最多前k个字符串， * 具体为： * 1.k在TopKRecord实例生成时指定，并且不再变化(k是构造函数的参数)。 * 2.含有add(String str)方法，即向TopKRecord中加入字符串。 * 3.含有printTopK()方法，即打印加入次数最多的前k个字符串，打印有哪些字符串和对应的次数即可，不要求严格按排名顺序打印。 * * 【举例】 * TopKRecord record = new TopKRecord(2); // 打印Top2的结构 * record.add("A"); * record.printTopK(); * 此时打印： * TOP: * Str: A Times: 1 * * record.add("B"): * record.add("B"); * record.printTopK(); * 此时打印： * TOP: * Str: A Times: 1 * Str: B Times: 2 * 或者打印 * TOP: * Str: B Times: 2 * Str: A Times: 1 * * record.add("C"); * record.add("C"); * record.printTopK(); * 此时打印： * TOP: * Str: B Times: 2 * Str: C Times: 2 * 或者打印 * TOP: * Str: C Times: 2 * Str: B Times: 2 * * 【要求】 * 1.在任何时刻，add方法的时问复杂度不超过O(logk)。 * 2.在任何时刻，printTopK方法的时间复杂度不超过O(k)。 * * 【难度】 * 原问题：中等 * 进阶问题：困难 * * 【解答】 * 原问题。首先遍历strArr并统计字符串的词频，例如，strArr=["a","b","b"，"a"，"c"]，遍历后可以生成每种字符串及其相关 * 词频的哈希表如下。 * 用哈希表的每条信息可以生成Node类的实例，Node类如下。 * 哈希表中有多少信息，就建立多少Node类的实例，并且依次放入堆中，具体过程为： * 1.建立一个大小为k的小根堆，这个堆放入的是Node类的实例。 * 2.遍历哈希表的每条记录，假设一条记录为(s,t)，s表示一种字符串，s的词频为t，则生成Node类的实例，记为(str,times)。 * 1）如果小根堆没有满，就直按将(str,times)加入堆，然后进行建堆调整(heapInsert调整)，堆中Node类实例之间都以词频 * (times)来进行比较，词频越小，位置越往上。 * 2）如果小根堆已满，说明此时小根堆已经选出k个最高词频的字符串，那么整个小根堆的堆顶自然代表已经选出的k个最高词频的字符 * 串中，词频最低的那个。堆顶的元素记为(headStr,minTimes)。如果minTimes<times，说明字符串str有资格进入当前k个最高 * 词频字符串的范围。而headStr应该被移出这个范围，所以把当前的堆顶(headStr,minTimes)替换成(str,times)，然后从堆顶 * 的位置进行堆的调整(heapify)。如果minTimes>=times，说明字符串str没有资格进入当前k个最高词频字符串的范围，因为str * 的词频还不如目前选出的k个最高词频字符串中词频最少的那个，所以什么也不做。 * 3.遍历完strArr之后，小根堆里就是所有字符串中k个最高词频的字符串，但要求严格按排名打印，所以还需要根据词频从大到小完成 * k个元素间的排序。 * 遍历strArr建立哈希表的过程为O(N)。哈希表中记录的条数最多为N条，每一条记录进堆时，堆的调整时间复杂度为O(logk)，所以 * 根据记录更新小根堆的过程为O(Nlogk)。k条记录排序的时间复杂度为O(klogk)。所以总的时间复杂度为 * O(N)+O(Nlogk)+O(klogk)，即O(Nlogk)。 * 具体过程请参看如下代码中的printTopKAndRank方法。 * * 进阶问题。原问题是已经存在不再变化的字符串数组，所以可以一次性统计词频哈希表，然后建小根堆。可是进阶问题不一样，每个字 * 符串词频可能会随时增加，这个过程一直是动态的。当然也可以在加入一个字符串时，在词频哈希表中增加这种字符串的词频，这样， * add方法的时间复杂度就是O(1)。可是当有printTopK操作时，你只能像原问题一样，根据所有字符串的词频表来建立小根堆，假设 * 此时哈希表的记录数为N，那么printTopK方法的时间复杂度就成了O(Nlogk)，但明显是不达标的。本文提供的解法依然是利用小根 * 堆这个数据结构，但在设计上更复杂。下面介绍TopKRecord的结构设计。 * TopKRecord结构重要的4个部分如下： * •依然有一个小根堆heap。小根堆里装的依然是原问题中Node类的实例，每个实例表示一个字符串及共词频统计的信息。小根堆里装的 * 都是加入过的所有字符串中词频最高的TopK。heap的大小在初始化时就确定，是Node类型的数组结构，数组的总大小为k。 * •整型变量index。表示如果新的Node类的实例想加入到heap，该放在heap的哪个位置。 * •哈希表strNodeMap。key为字符串类型，表示加入的某种字符串。value为Node类型。strNodeMap上的每条信息表示一种字符串 * 及其所对应的Node实例。 * •哈希表nodeIndexMap，key为Node类型，表示一种字符串及其词频信息。value为整型，表示key这个Node类的实例对应到heap * 上的位置，如果不在heap上，为-1。 * * 关于strNodeMap和nodeIndexMap的说明如下： * 比如，"A"这个字符串加入了10次，那么在strNodeMap表中就会有类似这样的记录(key="A",value=("A",10))，value是一个 * Node类的实例。如果"A"加入的次数很多，使"A"成为加入的所有字符中词频最高的TopK之一，那么"A"应该在堆上。假设"A"在堆上 * 的位置为5，那么在nodeIndexMap表中就会有类似这样的记录(key=("A",10),value=5)。如果"A"加入的次数不算多，没有使 * "A"成为加入的所有字符中词频最高的TopK之一，那么"A"不在堆上，则在nodeIndexMap表中就会有这样的记录 * (key=("A",10),value=-1)。strNodeMap是字符串及其所对应的Node实例信息的哈希表，nodeIndexMap是字符串的Node实例 * 信息对应在堆中(heap)位置的哈希表。 * * 以下为加入一个字符串时，TopKRecord类中add方法所做的事情： * 1.当加入一个字符串时，假设为str。首先在strNodeMap中查询str之前出现的词频，如果查不到，说明str为第一次出现，在 * strNodeMap中加入一条记录(key=str,value=(str,1))。如果可以查到，说明str之前出现过，此时需要把str的词频增加，假 * 设之前出现过10次，那么查到的记录为(key=str,value=(str,10))，变更为(key=str,value=(str,11))。 * 2.建立或调整完str的Node实例信息之后，需要考虑这个Node的实例信息是否已经在堆上，通过查询nodeIndexMap表可以得到 * Node的实例对应的堆上的位置，如果没有或者查询结果为-1，表示不在堆上，否则表示在堆上，位置记为pos。 * 1）如果在堆上，说明str词频没增加之前就是TopK之一，现在词频既然增加了，就需要考虑调整str对应的Node实例信息在堆中的位 * 置，从pos位置开始向下调整小根堆即可(heapify)。特别注意：为了保证nodeIndexMap表中位置信息的始终准确，调整堆时，每一 * 次两个堆元素(Node实例)之间的位置交换都要更新在nodeIndexMap表中的位置。比如，在堆上的一个Node实例("A",10)原来在2 * 位置，在nodeIndexMap表中的信息为(key=("A",10),value=2)。现在又加入了一个"A"，词频增加，信息当然要变成 * (key=("A",11),value=2)。然后从位置2调整堆时，发现这个实例需要和自己的一个孩子实例("B",10)交换，假设这个Node实例 * 的位置是6，即在nodeIndexMap表中记录为(key=("B",10),value=6)。那么在彼此交换位置之后，在heap数组中的两个实例当 * 然很容易互换位置，但同时在nodeIndexMap上各自的信息也要变更，分别变更为(key=("A",11),value=6)， * (key=("B",10),value=2)。也就是说，任何Node实例在堆中的位置调整都要改相应的nodeIndexMap表信息，这也是整个 * TopKRecord结构设计中最关键的逻辑。 * 2）如果不在堆中，则看当前的小根堆是否已满(index==k)。如果没有满(index<k)，那么把str的Node实例放入堆底(heap的 * index位置)，自然也要在nodeIndexMap表中加上位置信息。然后做堆在插入时的调整(heapInsert)，同样，任何交换都要改 * nodeIndexMap表。如果已满(index==k)，则看str的词频是否大于小根堆堆顶的词频(heap[0])，如果不大于，则什么都不做。 * 如果大于堆顶的词频，把str的Node实例设为新的堆顶，然后从位置0开始向下调整堆(heapify)，同样，任何堆中位置的变更都要改 * nodeIndexMap表。 * 3.过程结束。 * * 在加入新的字符串时，都可能会调整堆，而堆最大也仅是k的大小，所以add方法时间复杂度为O(logk)。随时更新的小根堆就是每时 * 每刻的TopK，打印时又没有排序的要求，所以printTopK方法直接依次打印小根堆数组即可，时间复杂度为O(K)。 * TopKRecord类的全部实现请参看如下代码。 * * @author Created by LiveEveryDay */ public class AppearTimesTopKProblem2 { public static class Node { public String str; public int times; public Node(String s, int t) { str = s; times = t; } } public static class TopKRecord { private final Node[] heap; private int index; private final HashMap<String, Node> strNodeMap; private final HashMap<Node, Integer> nodeIndexMap; public TopKRecord(int size) { heap = new Node[size]; index = 0; strNodeMap = new HashMap<>(); nodeIndexMap = new HashMap<>(); } public void add(String str) { Node curNode = null; int preIndex = -1; if (!strNodeMap.containsKey(str)) { curNode = new Node(str, 1); strNodeMap.put(str, curNode); nodeIndexMap.put(curNode, -1); } else { curNode = strNodeMap.get(str); curNode.times++; preIndex = nodeIndexMap.get(curNode); } if (preIndex == -1) { if (index == heap.length) { if (heap[0].times < curNode.times) { nodeIndexMap.put(heap[0], -1); nodeIndexMap.put(curNode, 0); heap[0] = curNode; heapify(0, index); } } else { nodeIndexMap.put(curNode, index); heap[index] = curNode; heapInsert(index++); } } else { heapify(preIndex, index); } } public void printTopK() { System.out.println("TOP: "); for (int i = 0; i != heap.length; i++) { if (heap[i] == null) { break; } System.out.print("Str: " + heap[i].str); System.out.println(" Times: " + heap[i].times); } } private void heapInsert(int index) { while (index != 0) { int parent = (index - 1) >> 1; if (heap[index].times < heap[parent].times) { swap(parent, index); index = parent; } else { break; } } } private void heapify(int index, int heapSize) { int l = index * 2 + 1; int r = index * 2 + 2; int smallest = index; while (l < heapSize) { if (heap[l].times < heap[index].times) { smallest = l; } if (r < heapSize && heap[r].times < heap[smallest].times) { smallest = r; } if (smallest != index) { swap(smallest, index); } else { break; } index = smallest; l = index * 2 + 1; r = index * 2 + 2; } } private void swap(int index1, int index2) { nodeIndexMap.put(heap[index1], index2); nodeIndexMap.put(heap[index2], index1); Node tmp = heap[index]; heap[index1] = heap[index2]; heap[index2] = tmp; } } public static void main(String[] args) { TopKRecord record = new TopKRecord(5); record.add("C"); record.add("D"); record.add("D"); record.add("E"); record.add("E"); record.printTopK(); } } // ------ Output ------ /* TOP: Str: C Times: 1 Str: D Times: 2 Str: E Times: 2 */