分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程大家好欢迎来到我的网站 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑人工智能时代就要来临了科… 继续阅读 前言https://www.captainai.net/troubleshooterpackage live.every.day.ProgrammingDesign.CodingInterviewGuide.ArrayAndMatrix; import java.util.Arrays; /** * 找到无序数组中最小的k个数 * * 【题目】 * 给定一个无序的整型数组arr找到其中最小的k个数。 * * 【要求】 * 如果数组arr的长度为N排序之后自然可以得到最小的k个数此时时间复杂度与排序的时间复杂度相同均为O(NlogN)。本题要求 * 读者实现时间复杂度为O(Nlogk)和O(N)的方法。 * * 【难度】 * O(Nlogk)的方法中等 * O(N)的方法非常困难 * * 【解答】 * 依靠把arr进行排序的方法太简单时间复杂度也不好所以本文不再详述。 * O(Nlogk)的方法。说起来也非常简单就是一直维护一个有k个数的大根堆这个堆代表目前选出的k个最小的数在堆里的k个元素 * 中堆顶的元素是最小的k个数里最大的那个。 * 接下来遍历整个数组遍历的过程中看当前数是否比堆顶元素小。如果是就把堆顶的元素替换成当前的数然后从堆顶的位罝调整整 * 个堆让替换操作后堆的最大元素继续处在堆顶的位置如果不是则不进行任何操作继续遍历下一个数在遍历完成后堆中的k * 个数就是所有数组中最小的k个数。 * 具体请参看如下代码中的getMinKNumsByHeap方法代码中的heapInsert和heapify方法分别为堆排序中的建堆和调整堆的实现。 * * author Created by LiveEveryDay */ public class FindUnorderedArrayMinKNum1 { public static int[] getMinKNumsByHeap(int[] arr, int k) { if (k 1 || k arr.length) { return arr; } int[] kHeap new int[k]; for (int i 0; i ! k; i) { heapInsert(kHeap, arr[i], i); } for (int i k; i ! arr.length; i) { if (arr[i] kHeap[0]) { kHeap[0] arr[i]; heapify(kHeap, 0, k); } } return kHeap; } private static void heapInsert(int[] arr, int value, int index) { arr[index] value; while (index ! 0) { int parent (index - 1) / 2; if (arr[parent] arr[index]) { swap(arr, parent, index); index parent; } else { break; } } } private static void heapify(int[] arr, int index, int heapSize) { int left index * 2 1; int right index * 2 2; int largest index; while (left heapSize) { if (arr[left] arr[index]) { largest left; } if (right heapSize arr[right] arr[largest]) { largest right; } if (largest ! index) { swap(arr, largest, index); } else { break; } index largest; left index * 2 1; right index * 2 2; } } private static void swap(int[] arr, int index1, int index2) { int tmp arr[index1]; arr[index1] arr[index2]; arr[index2] tmp; } public static void main(String[] args) { int[] arr {6, 5, 4, 8, 3, 9, 2, 0, 1, 5, 8}; int k 3; System.out.printf(Arrays.toString(getMinKNumsByHeap(arr, k))); } } // ------ Output ------ /* [2, 0, 1] */