目录

• 前言
• 问题介绍
• 解决方案
• 代码编写
• • java语言版本
  • c语言版本
  • c++语言版本
• 思考感悟
• 写在最后

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定一个二维数组，arr，arr代表arr.length个数组，且每一个数组都是排好序的(从小到大)，给定一个整数k，求arr.length个数组中最大的topk数组
如：
arr=[12345635891014]\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 5 & 8 \\ 9 & 10 & 14 \end{bmatrix}​139​2510​3814​456​
k = 5
结果为 {14,10,9,8,6}

解决方案

原问题：
1、创建一个数据结构HeapNode，其中存在三个属性：当前数值，当前数所在数组的横坐标，纵坐标
2、创建HeapNode数组，长度为数组个数len，
3、将数组中的最后一个数放入HeapNode，HeapNode每放入一个值都进行堆上浮操作
4、循环弹出堆顶（最大值），弹出时如果堆顶值的纵坐标越界（所在数组遍历完毕），则堆顶弹出，堆底替换上来，并重新调整堆，堆大小减1.
5、如果没有越界，则取所在数组的下一个值替换堆顶，重新调整堆即可。

代码编写

java语言版本

原问题：
方法一:

    /*** 二轮测试：打印n个数组的topk* @param arr* @return*/public static int[] getTopKFormNArr(int[][] arr, int k) {if (arr == null || arr.length == 0 || arr[0].length == 0) {return null;}// 大小为n的堆HeapNode[] heap = new HeapNode[arr.length];int indexForHeap = 0;for (int i = 0; i < arr.length; i++) {// 数组从小到大，所以放每一行数组的最后一个数heapInsertCp1(heap, indexForHeap,new HeapNode(arr[i][arr[i].length-1], i, arr[i].length-1));indexForHeap++;}int[] res = new int[k];// 开始计算Topk,弹出k个值for (int i = 0; i < k; i++) {HeapNode top = heap[0];// 每一次都是堆顶res[i] = top.getValue();// 堆顶需要弹出:如果堆顶不是自己队列最后一个数，则自己队列找到顶替者，否则堆大小减少一个if (top.getIndex() == 0) {// 最后一个数,则将头替换成尾巴heap[0] = heap[indexForHeap-1];// 减少一个长度indexForHeap--;}else {// 不是最后一个数,找到顶替者heap[0] = new HeapNode(arr[top.getArrayID()][top.getIndex()-1], top.getArrayID(), top.getIndex()-1);// 下沉heapifyCp1(heap, indexForHeap);}}return res;}/*** 从顶开始下城* @param heap* @param len*/private static void heapifyCp1(HeapNode[] heap, int len) {int parent = 0;int left = (2 * parent) + 1;while (left < len) {int maxIndex = heap[parent].getValue() > heap[left].getValue() ? parent : left;int right = left + 1;if (right < len && heap[right].getValue() > heap[parent].getValue()) {maxIndex = right;}if (maxIndex == parent) {break;}else {swap(heap, parent, maxIndex);}parent = maxIndex;left = (2*parent)+1;}}/*** 将heapnode插入heap中并上浮* @param heap* @param index* @param heapNode*/private static void heapInsertCp1(HeapNode[] heap, int index, HeapNode heapNode) {heap[index] = heapNode;// 上浮int cur = index;while (cur != 0) {int parent = (cur-1)/2;if (heap[parent].getValue() < heap[cur].getValue()) {// 上浮swap(heap, parent, cur);}cur = parent;}}public static void main(String[] args) {CommonUtils.printArr(        getTopKFormNArr(new int[][]{{1,2,3,4,5,6},{3,5,8},{9,10,14}}, 5));}

数据结构：

public class HeapNode {/*** 节点值*/int value;/*** 所在数组Id*/int arrayID;/*** 在所在数组的第几个地方*/int index;public HeapNode(int value, int arrayID, int index) {this.value = value;this.arrayID = arrayID;this.index = index;}public int getValue() {return value;}public void setValue(int value) {this.value = value;}public int getArrayID() {return arrayID;}public void setArrayID(int arrayID) {this.arrayID = arrayID;}public int getIndex() {return index;}public void setIndex(int index) {this.index = index;}
}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这道题的思想很适合大数据分片求topk值的思想，本来看到大数据的面试题有这种类型的题目，但是一直具体实现细节没有仔细研究过，这里刚好遇到这种类型的题目，可以做一下笔记~
还有大数据分类可以使用hash方式将相同的值分布到同一个文件中，去重和判重非常有效。

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！