分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter
package live.every.day.ProgrammingDesign.CodingInterviewGuide.ArrayAndMatrix; /** * 打印N个数组整体最大的TopK * * 【题目】 * 有N个长度不一的数组，所有的数组都是有序的，请从大到小打印这N个数组整体最大的前K个数。 * 例如，输入含有N行元素的二维数组可以代表N个一维数组。 * 219,405,538,845,971 * 148,558 * 52,99,348,691 * 再输入整数k=5，则打印： * Top5：971,845,691,558,538 * * 【要求】 * 1.如果所有数组的元素个数小于K，则从大到小打印所有的数。 * 2.要求时间复杂度为O(KlogN)。 * * 【难度】 * 中等 * * 【解答】 * 本题的解法是利用堆结构和堆排序的过程完成的，具体过程如下： * 1.构建一个大小为N的大根堆heap，建堆的过程就是把每一个数组中的最后一个值，也就是该数组的最大值，依次加入到堆里，这个过 * 程是建堆时的调整过程(heapInsert)。 * 2.建好堆之后，此时heap堆顶的元素是所有数组的最大值中最大的那个，打印堆顶元素。 * 3.假设堆顶元素来自a数组的i位置。那么接下来就把堆顶的前一个数（即a[i-1]）放在heap的头部，也就是用a[i-1]替换原本的堆 * 顶，然后从堆的头部开始调整堆，使其重新变为大根堆（heapify过程）。 * 4.这样每次都可以得到一个堆顶元素max，在打印完成后都经历步骤3的调整过程。整体打印k次，就是从大到小全部的TopK。 * 5.在重复步骤3的过程中，如果max来自的那个数组（仍假设是a数组）已经没有元素。也就是说，max已经是a[0]，再往左没有数了。 * 那么就把heap中最后一个元素放在heap头部的位置，然后把heap的大小减1（heapSize-1），最后依然是从堆的头部开始调整堆， * 使其重新变为大根堆（堆大小减1之后的heapify过程）。 * 6.直到打印了k个数，过程结束。 * * 为了知道每一次的max来自什么数组的什么位置，放在堆里的元素是如下的HeapNode类。 * * 整个打印过程请参看如下代码中的printTopK方法。 * * @author Created by LiveEveryDay */ public class PrintNArrayTopK { public static class HeapNode { public int value; // 值是什么 public int arrNum; // 来自哪个数组 public int index; // 来自数组的哪个位置 public HeapNode(int value, int arrNum, int index) { this.value = value; this.arrNum = arrNum; this.index = index; } } public static void printTopK(int[][] matrix, int topK) { int heapSize = matrix.length; HeapNode[] heap = new HeapNode[heapSize]; for (int i = 0; i != heapSize; i++) { int index = matrix[i].length - 1; heap[i] = new HeapNode(matrix[i][index], i, index); heapInsert(heap, i); } System.out.println("TOP " + topK + " : "); for (int i = 0; i != topK; i++) { if (heapSize == 0) { break; } System.out.print(heap[0].value + " "); if (heap[0].index != 0) { heap[0].value = matrix[heap[0].arrNum][--heap[0].index]; } else { swap(heap, 0, --heapSize); } heapify(heap, 0, heapSize); } } public static void heapInsert(HeapNode[] heap, int index) { while (index != 0) { int parent = (index - 1) >> 1; if (heap[parent].value < heap[index].value) { swap(heap, parent, index); index = parent; } else { break; } } } public static void heapify(HeapNode[] heap, int index, int heapSize) { int left = index * 2 + 1; int right = index * 2 + 2; int largest = index; while (left < heapSize) { if (heap[left].value > heap[index].value) { largest = left; } if (right < heapSize && heap[right].value > heap[largest].value) { largest = right; } if (largest != index) { swap(heap, largest, index); } else { break; } index = largest; left = index * 2 + 1; right = index * 2 + 2; } } public static void swap(HeapNode[] heap, int index1, int index2) { HeapNode tmp = heap[index1]; heap[index1] = heap[index2]; heap[index2] = tmp; } public static void main(String[] args) { int[] arr1 = {219, 405, 538, 845, 971}; int[] arr2 = {148, 558}; int[] arr3 = {52, 99, 348, 691}; int[][] matrix = new int[][]{arr1, arr2, arr3}; int topK = 5; printTopK(matrix, topK); } } // ------ Output ------ /* TOP 5 : 971 845 691 558 538 */
