分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程大家好欢迎来到我的网站 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑人工智能时代就要来临了科… 继续阅读 前言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)的方法相当困难 * * 【解答】 * O(N)的解法。需要用到一个经典的算法--BFPRT算法该算法手1973年由Blum、Floyd、Pratt、Rivest和Tarjan联合发明其 * 中蕴含的深刻思想改变了世界。BFPRT算法解决了这样一个问题在时间复杂度O(N)内从无序的数组中找到第k小的数。显而易见的 * 是如果我们找到了第k小的数那么想求arr中最小的k个数就是再遍历一次数组的工作量而已所以关键问题就变成了如何理解并 * 实现BFPRT算法。 * * BFPRT算法是如何找到第k小的数以下是BFPRT算法的过程假设BFPRT算法的函数是int select(int[]arr,k)该函数的功能 * 为在arr中找到第k小的数然后返回该数。 * select(arrk)的过程如下 * 1.将arr中的n个元素划分成n/5组每组5个元素如果最后的组不够5个元素那么最后剩下的元素为一组(n%5个元素)。 * 2.对每个组进行插入排序只针对每个组最多5个元素之间的组内排序组与组之间并不排序。排序后找到每个组的中位数如果组的 * 元素个数为偶数这里规定找到下中位数。 * 3.步骤2中一共会找到n/5个中位数让这些中位数组成一个新的数组记为mArr。递归调用select(mArr,mArr.length/2)意 * 义是找到mArr这个数组中的中位数即mArr中的第(mArr.length/2)小的数。 * 4.假设步骤3中递归调用select(mArr,mArr.length/2)后返回的数为x。根据这个x划分整个arr数组(partition过程)划分 * 的过程为在arr中比x小的数都在x的左边大于x的数都在x的右边x在中间。假设划分完成后x在arr中的位置记为i。 * 5.如果ik说明×为整个数组中第k小的数直接返回。 * •如果ik说明x处在第k小的数的左边应该在x的右边寻找第k小的数所以递归调用select函数在左半区寻找第k小的数。 * •如果ik说明x处在第k小的数的右边应该在x的左边寻找第k小的数所以递归调用select函数在右半区寻找第(i-k)小的数。 * * BFPRT算法为什么在时间复杂度上可以做到稳定的O(N)呢以下是BFPRT的时间复杂度分析我们假设BFPRT算法处理大小为N的数组 * 时时间复杂度函数为T(N)。 * 1.如上过程中除了步骤3和步骤5要递归调用select两数之外其他所有的处理过程都可以在O(N)的时间内完成。 * 2.步骤3中有递归调用select的过程且递归处理的数组大小最大为n/5即T(N/5)。 * 3.步骤5也递归调用了select那么递归处理的数组大小最大为多少呢具体地说我们关心的是由x划分出的左半区最大有多大和由 * x划分出的左半区最大有多大。以下是右半区域的大小计算过程(左半区域的计算过程也类似)这也是整个BFPRT算法的精髓。 * •因为x是5个数一组的中位数组成的数组(mArr)中的中位数所以在mArr中(mArr大小为N/5)有一半的数(N/10个)都比x要小。 * •所有在mArr中比x小的所有数在各自的组中又肯定比2个数要大因为在mArr中的每一个数都是各自组中的中位数。 * •所以至少有((N/10)×3的数比x要小这里必须减去两个特殊的组一个是x自己所在的组一个是可能元素数量不足5个的组所以 * 至少有(N/10-2)×3的数比x要小。 * •既然至少有(N/10-2)x3的数比x要小那么至多有N-(N/10-2)x3的数比x要大也就是7N/106个数比x要大即右半区最大的量。 * •左半区可以用类似的分析过程求出依然是至多有7N/106个数比x要小。 * 所以整个步骤5的复杂度为T(7N/106)。 * 综上所述T(N)O(N)T(N/5)T(7N/106)可以在数学上证明T(N)的复杂度就是O(N)详细证明过程请参看相关图书 * (例如《算法导论》中9.3节的内容)本文不再详述。 * * 为什么要如此费力地这么处理arr数组呢要5个数分1组又要求中位数的中位数还要划分好麻烦。这是因为以中位数的中位数x * 划分的数组可以在步骤5的递归时确保肯定淘汰一定的数据量起码淘汰掉3N/10-6的数据量。 * 不得不说的是关于选择划分元素的问题很多实现都是随便找一个数进行数组的划分也就是类似随机快速排序的划分方式这种划 * 分方式无法达到时间复杂度为O(N)的原因是不能确定淘汰的数据量而BFPRT算法在划分时使用的是中位数的中位数进行划分从而 * 确定了淘汰的数据量最后成功地让时间复杂度收敛到O(N)的程度。 * 本文的实现对BFPRT算法做了更好的改进主要改进的地方是当中位数的中位数x在arr中大量出现的时候那么在划分之后到底返回 * 什么位置上的×呢 * 在本文的实现中返回在通过x划分arr后等于x的整个位置区间。比如pivotRange[a,b]表示arr[a..b]上都是x并以此区 * 间去命中第k小的数如果在[a,b]上就是命中如果没在[a,b]上表示没命中。这样既可以尽量少地进行递归过程又可以增加 * 淘汰的数据量使得步骤5的递归过程变得数据量更少。 * * 具体过程请参看如下代码中的getMinKNumsByBFPRT方法。 * * author Created by LiveEveryDay */ public class FindUnorderedArrayMinKNum2 { public static int[] getMinKNumsByBFPRT(int[] arr, int k) { if (k 1 || k arr.length) { return arr; } int minKth getMinKthByBFPRT(arr, k); int[] res new int[k]; int index 0; for (int i 0; i ! arr.length; i) { if (arr[i] minKth) { res[index] arr[i]; } } for (; index ! res.length; index) { res[index] minKth; } return res; } private static int getMinKthByBFPRT(int[] arr, int K) { int[] copyArr copyArray(arr); return select(copyArr, 0, copyArr.length - 1, K - 1); } private static int[] copyArray(int[] arr) { int[] res new int[arr.length]; System.arraycopy(arr, 0, res, 0, res.length); return res; } private static int select(int[] arr, int begin, int end, int i) { if (begin end) { return arr[begin]; } int pivot medianOfZMedians(arr, begin, end); int[] pivotRange partition(arr, begin, end, pivot); if (i pivotRange[0] i pivotRange[1]) { return arr[i]; } else if (i pivotRange[0]) { return select(arr, begin, pivotRange[0] - 1, i); } else { return select(arr, pivotRange[1] 1, end, i); } } private static int medianOfZMedians(int[] arr, int begin, int end) { int num end - begin 1; int offset num % 5 0 ? 0 : 1; int[] mArr new int[num / 5 offset]; for (int i 0; i mArr.length; i) { int beginI begin i * 5; int endI beginI 4; mArr[i] getMedian(arr, beginI, Math.min(end, endI)); } return select(mArr, 0, mArr.length - 1, mArr.length / 2); } private static int[] partition(int[] arr, int begin, int end, int pivotValue) { int small begin - 1; int cur begin; int big end 1; while (cur ! big) { if (arr[cur] pivotValue) { swap(arr, small, cur); } else if (arr[cur] pivotValue) { swap(arr, cur, --big); } else { cur; } } int[] range new int[2]; range[0] small 1; range[1] big - 1; return range; } private static int getMedian(int[] arr, int begin, int end) { insertionSort(arr, begin, end); int sum end begin; int mid (sum / 2) (sum % 2); return arr[mid]; } private static void insertionSort(int[] arr, int begin, int end) { for (int i begin 1; i ! end 1; i) { for (int j i; j ! begin; j--) { if (arr[j - 1] arr[j]) { swap(arr, j - 1, j); } else { break; } } } } 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(getMinKNumsByBFPRT(arr, k))); } } // ------ Output ------ /* [0, 1, 2] */