分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程大家好欢迎来到我的网站 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑人工智能时代就要来临了科… 继续阅读 前言https://www.captainai.net/troubleshooterpackage live.every.day.ProgrammingDesign.CodingInterviewGuide.Other; import java.util.HashMap; /** * 出现次数的TOPK问题 * * 【题目】 * 给定String类型的数组strArr再给定整数k请严格按照排名顺序打印出现次数前k名的字符串。 * * 【举例】 * strArr[1,2,3,4]k2 * No.1: 1, times: 1 * No.2: 2, times: 1 * 这种情况下所有的字符串都出现一样多随便打印任何两个字符串都可以。 * * strArr[1,1,2,3]k2 * 输出 * 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,bac]遍历后可以生成每种字符串及其相关 * 词频的哈希表如下。 * 用哈希表的每条信息可以生成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)。如果minTimestimes说明字符串str有资格进入当前k个最高 * 词频字符串的范围。而headStr应该被移出这个范围所以把当前的堆顶(headStr,minTimes)替换成(str,times)然后从堆顶 * 的位置进行堆的调整(heapify)。如果minTimestimes说明字符串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实例。 * •哈希表nodeIndexMapkey为Node类型表示一种字符串及其词频信息。value为整型表示key这个Node类的实例对应到heap * 上的位置如果不在heap上为-1。 * * 关于strNodeMap和nodeIndexMap的说明如下 * 比如A这个字符串加入了10次那么在strNodeMap表中就会有类似这样的记录(keyA,value(A,10))value是一个 * Node类的实例。如果A加入的次数很多使A成为加入的所有字符中词频最高的TopK之一那么A应该在堆上。假设A在堆上 * 的位置为5那么在nodeIndexMap表中就会有类似这样的记录(key(A,10),value5)。如果A加入的次数不算多没有使 * A成为加入的所有字符中词频最高的TopK之一那么A不在堆上则在nodeIndexMap表中就会有这样的记录 * (key(A,10),value-1)。strNodeMap是字符串及其所对应的Node实例信息的哈希表nodeIndexMap是字符串的Node实例 * 信息对应在堆中(heap)位置的哈希表。 * * 以下为加入一个字符串时TopKRecord类中add方法所做的事情 * 1.当加入一个字符串时假设为str。首先在strNodeMap中查询str之前出现的词频如果查不到说明str为第一次出现在 * strNodeMap中加入一条记录(keystr,value(str,1))。如果可以查到说明str之前出现过此时需要把str的词频增加假 * 设之前出现过10次那么查到的记录为(keystr,value(str,10))变更为(keystr,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),value2)。现在又加入了一个A词频增加信息当然要变成 * (key(A,11),value2)。然后从位置2调整堆时发现这个实例需要和自己的一个孩子实例(B,10)交换假设这个Node实例 * 的位置是6即在nodeIndexMap表中记录为(key(B,10),value6)。那么在彼此交换位置之后在heap数组中的两个实例当 * 然很容易互换位置但同时在nodeIndexMap上各自的信息也要变更分别变更为(key(A,11),value6) * (key(B,10),value2)。也就是说任何Node实例在堆中的位置调整都要改相应的nodeIndexMap表信息这也是整个 * TopKRecord结构设计中最关键的逻辑。 * 2如果不在堆中则看当前的小根堆是否已满(indexk)。如果没有满(indexk)那么把str的Node实例放入堆底(heap的 * index位置)自然也要在nodeIndexMap表中加上位置信息。然后做堆在插入时的调整(heapInsert)同样任何交换都要改 * nodeIndexMap表。如果已满(indexk)则看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 HashMapString, Node strNodeMap; private final HashMapNode, 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 */