企业官网建设流程全解析

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter

package 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] */