前言
当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~
问题介绍
原问题
设计一个数据结构，该数据结构有以下几个功能：
1、能够无限接收字符串类型的元素
2、能够随时打印所有出现的字符串中，出现次数最多的字符串
解决方案
原问题：
1、首先设计一个容器record能够存储当前字符串和当前字符串出现的次数
2、数据结构中含有两个重要的数据结构：一个是小根堆（元素类型为Record），一个是map，map中key为Record，value为当前Record在堆数组中的位置，如果是-1说明不在堆中
3、获取出现次数最多的topk字符串直接将堆中的值全部遍历输出即可
4、加入一个元素时，应该做如下判断：
- 首先判断该元素是否已经出现过，通过map进行判断，没有的话则加入map，增加次数，有的话直接增加次数
- 其次查看当前元素是否在堆中，如果在，则直接直接定位到堆位置进行下沉操作，如果不在则判断堆是否满了，如果没满直接放入，如果满了则判断出现次数是否大于堆顶，大于的话则将堆顶弹出，插入当前元素即可，如果小于堆顶，则什么都不做
代码编写
java语言版本
原问题：
原问题：
public class TopKRecordCp1 {
/**
* 小根堆结构
*/
private CommonHeapPlus<Record> heap;
/**
* 用于判断用户当前输入的是否已经有了
*/
private Map<String, Record> mapStringRecord;
/**
* 用于判断当前记录对象是否在堆中，如果不存在为-1，如果存在则可以直接定位到堆位置
*/
private Map<Record, Integer> mapRecordInteger;
public TopKRecordCp1(int k) {
// 小根
this.heap = new CommonHeapPlus<>(k, new Comparator<Record>() {
@Override
public int compare(Record o1, Record o2) {
return o2.getTimes() - o1.getTimes();
}
});
mapStringRecord = new HashMap<>();
mapRecordInteger = new HashMap<>();
}
/**
* 加入一个str
* @param str
*/
public void add(String str) {
if (str == null) {
return;
}
Record cur = null;
// 先处理第一个map
if (mapStringRecord.containsKey(str)) {
cur = mapStringRecord.get(str);
cur.setTimes(cur.getTimes()+1);
if (mapRecordInteger.containsKey(cur) && mapRecordInteger.get(cur) >= 0) {
// 已经在堆中
heap.heapify(mapRecordInteger.get(cur));
return;
}
// 不再堆中的逻辑可以和下面一样
}else {
cur = new Record(str, 1);
mapStringRecord.put(str, cur);
}
// 到这里说明不管cur是否是老str，都不在堆中，所以现在判断是否应该加入堆
// 看下堆是否满了
if (!heap.isFull()) {
//没有满直接放进去，返回所在堆的index
heap.heapInsetForTopK(cur, mapRecordInteger);
// 更新indexmap
//mapRecordInteger.put(cur, curIndex);
}else{
// 满了的话需要判断是否有资格进去
if (heap.getHead().getTimes() >= cur.getTimes()) {
// 连最小值都大于当前的times，没资格进堆
mapRecordInteger.put(cur, -1);
}else {
// 有资格进堆
heap.popHead();
heap.heapInsetForTopK(cur, mapRecordInteger);
//int curIndex = heap.heapInsert(cur);
//mapRecordInteger.put(cur, curIndex);
}
}
}
/**
* 打印到目前为止的次数topk
*/
public void printTopK() {
while (!heap.isEmpty()) {
Record record = heap.popHead();
System.out.println("Str: " + record.getVlaue() + " Times : " + record.getTimes());
}
}
/**
* 存储两个变量
* value：用户输入的字符串
* times：该字符串目前出现的次数
*/
public class Record{
private String vlaue;
private int times;
public Record(String vlaue, int times) {
this.vlaue = vlaue;
this.times = times;
}
public String getVlaue() {
return vlaue;
}
public void setVlaue(String vlaue) {
this.vlaue = vlaue;
}
public int getTimes() {
return times;
}
public void setTimes(int times) {
this.times = times;
}
}
public static void main(String[] args) {
TopKRecordCp1 topKRecordCp1 = new TopKRecordCp1(2);
topKRecordCp1.add("1");
topKRecordCp1.add("1");
topKRecordCp1.add("2");
topKRecordCp1.add("3");
topKRecordCp1.printTopK();
}
}
通用堆结构
public class CommonHeapPlus<T> {
/**
* 堆数组
*/
private Object[] heap;
/**
* 堆大小
*/
private int index;
/**
* 比较规则:默认大根堆
*/
private Comparator<T> comparator;
/**
* 仿照Arraylist的初始化方式
* @param size
*/
public CommonHeapPlus(int size, Comparator<T> comparator) {
this.heap = new Object[size];
this.comparator = comparator;
}
/**
* 插入并上浮
* 返回最终插入的元素所在的位置
*/
public int heapInsert(T elm) {
if (index == heap.length) {
// 堆满了
throw new RuntimeException("堆满了,暂时不支持扩容");
}
heap[index++] = elm;
int cur = index - 1;
while (cur != 0) {
int parent = (cur-1)/2;
if (comparator.compare((T)heap[cur], (T)heap[parent]) > 0) {
CommonUtils.swapPlus(heap, parent, cur);
cur = parent;
}else {
break;
}
}
return cur;
}
/**
* 定制化接口
* @return
*/
public int heapInsetForTopK(T elm , Map<T, Integer> map) {
if (index == heap.length) {
// 堆满了
throw new RuntimeException("堆满了,暂时不支持扩容");
}
heap[index++] = elm;
int cur = index - 1;
// 初始化位置
map.put(elm, cur);
while (cur != 0) {
int parent = (cur-1)/2;
if (comparator.compare((T)heap[cur], (T)heap[parent]) > 0) {
CommonUtils.swapPlus(heap, parent, cur);
// 交换的时候需要更新index
map.put((T)heap[cur], cur);
map.put((T)heap[parent], parent);
cur = parent;
}else {
break;
}
}
return cur;
}
/**
* 下沉
*/
public void heapify(int head) {
int cur = head;
int left = (cur * 2) + 1;
while (left < index) {
int max = comparator.compare((T) heap[left], (T) heap[cur]) > 0 ? left : cur;
int right = left + 1;
while (right < index && comparator.compare((T)heap[right], (T) heap[max]) > 0) {
max = right;
}
if (max == cur) {
break;
}
CommonUtils.swapPlus(heap, cur, max);
cur = max;
left = (cur * 2) + 1;
}
}
public boolean isEmpty() {
return index == 0;
}
public boolean isFull() {
return index == heap.length;
}
public T getHead() {
return (T) heap[0];
}
/**
* 弹出头节点
* @return
*/
public T popHead() {
T res = (T) heap[0];
CommonUtils.swapPlus(heap, 0, index-1);
index--;
heapify(0);
return res;
}
/**
* 获取当前堆的大小
* @return
*/
public int getIndex() {
return index;
}
}
c语言版本
正在学习中
c++语言版本
正在学习中
思考感悟
有时候求最大的k个值问题需要用到的恰恰是小根堆，因为堆的特性是实时能够知道当前堆中的最小值和最大值，如果我们知道topK的最小值，才知道当前值是否能够进入堆，如果小于最小值，那么就会小于堆中的任何一个元素，自然没有资格进入堆中。
因此topK问题通常需要反着定义堆的比较规则，这个需要注意一下