在无序数组中找到第K小的数

在无序数组中找到第K小的数,时间复杂度要求是O(n).

解法一 改写快排

再学习bfprt算法之前，先看下，如何通过改写快排的方式实现，时间复杂是O(n)的算法。

什么是快排：
快速排序（Quick Sort）是一种高效的排序算法，它基于分治策略和递归实现。它的基本思想是将一个数组分成两个子数组，然后对这两个子数组分别进行排序，最终将两个有序的子数组合并成一个有序的数组。

使用任何关于排好序在拿值的方法都是不符合要求的，因此排序算法，最好的时间复杂度也是N * log N ；是不符合要求的，即使语言本身实现的也不符合要求。

这题我们就是借助快排里的分层的思想，来实现复杂度是O(n)，快排中会随机选中一个数字，然后将数组分成三部分，一部分是大于当前数字的，一部分等于当前数字的，一部分小于当前数字的，有了这三层，那么数组整体上就是有序的，在小范围内是无序的，根据整体有序，那么我们就可以抛掉两部分，只在符合要求的那一部分内继续去查找，这样就形成了剪枝的效果，使其复杂度降到O(n);

代码演示

 /*** 查找第k 小的数* @param array* @param k* @return*/public static int minKth2(int[] array, int k) {//为了不改变原数组int[] arr = copyArray(array);return process2(arr, 0, arr.length - 1, k - 1);}/*** 复制数组，* @param arr* @return*/public static int[] copyArray(int[] arr) {int[] ans = new int[arr.length];for (int i = 0; i != ans.length; i++) {ans[i] = arr[i];}return ans;}/***  // arr 第k小的数*     // process2(arr, 0, N-1, k-1)*     // arr[L..R]  范围上，如果排序的话(不是真的去排序)，找位于index的数*     // index [L..R]* @param arr* @param L* @param R* @param index* @return*/public static int process2(int[] arr, int L, int R, int index) {if (L == R) { // L = =R ==INDEXreturn arr[L];}// 随机选中一个数进行分层int pivot = arr[L + (int) (Math.random() * (R - L + 1))];int[] range = partition(arr, L, R, pivot);//刚好在选中的数字范围内，直接返回if (index >= range[0] && index <= range[1]) {return arr[index];} else if (index < range[0]) {//小于去左边继续搜return process2(arr, L, range[0] - 1, index);} else {//大于去右边搜return process2(arr, range[1] + 1, R, index);}}/*** 分层 小于在左边，大于在右边* 返回数组， 当前选中数字所在位置的左右边界* @param arr* @param L* @param R* @param pivot* @return*/public static int[] partition(int[] arr, int L, int R, int pivot) {int less = L - 1;int more = R + 1;int cur = L;while (cur < more) {if (arr[cur] < pivot) {swap(arr, ++less, cur++);} else if (arr[cur] > pivot) {swap(arr, cur, --more);} else {cur++;}}return new int[] { less + 1, more - 1 };}/*** 位置交换* @param arr* @param i1* @param i2*/public static void swap(int[] arr, int i1, int i2) {int tmp = arr[i1];arr[i1] = arr[i2];arr[i2] = tmp;}

bfprt 算法

bfprt 算法和上面改写快排的方法实际是类似的，区别在于进行数据分层时，我们改写快排中，是随机选中一个数字进行分层，这样是有一个问题，复杂度会根据选中数字的优劣变化，时间复杂度是O(n)是指其会收敛于O(n).

bfprt 算法，是要根据一个规则来选取用来分层的数，使其复杂度是个固定值，不是数学法证明收敛于某个值，
具体 规则如下：
1.数组中每五个元素分成一组，最后不够五个的，单独算一组
2.每个小组的元素，进行排序，
3.选取每组排序后的中间数字，组成一个新的小组
4.在把新小组的数字排序后，选择中间的数字，
通过这几步下来，选取的数字，就很接近中间数字了，这样就保证，每次都能舍弃将近一半的数字，从而让复杂度变成固定值，

代码演示

public class Demo22 {/*** bfprt 算法* @param array* @param k* @return*/public  int minKth3(int[] array, int k) {int[] arr = copyArray(array);return bfprt(arr, 0, arr.length - 1, k - 1);}// arr[L..R]  如果排序的话，位于index位置的数，是什么，返回public  int bfprt(int[] arr, int L, int R, int index) {if (L == R) {return arr[L];}// L...R  每五个数一组// 每一个小组内部排好序// 小组的中位数组成新数组// 这个新数组的中位数返回int pivot = medianOfMedians(arr, L, R);int[] range = partition(arr, L, R, pivot);if (index >= range[0] && index <= range[1]) {return arr[index];} else if (index < range[0]) {return bfprt(arr, L, range[0] - 1, index);} else {return bfprt(arr, range[1] + 1, R, index);}}/*** 分层 大的放左边，等于放中间，小于放右边。* @param arr* @param L* @param R* @param pivot* @return*/public int[] partition(int[]arr,int L,int R,int pivot){int more = L - 1;int less = R + 1;int cur = L;while (cur < less){if (arr[cur] > pivot){swap(arr,++more,cur++);} else if (arr[cur] < pivot) {swap(arr,cur,--less);}else{cur++;}}return new int[]{more + 1, less - 1};}// arr[L...R]  五个数一组// 每个小组内部排序// 每个小组中位数领出来，组成marr// marr中的中位数，返回public  int medianOfMedians(int[] arr, int L, int R) {int size = R - L + 1;int offset = size % 5 == 0 ? 0 : 1;int[] mArr = new int[size / 5 + offset];for (int team = 0; team < mArr.length; team++) {int teamFirst = L + team * 5;// L ... L + 4// L +5 ... L +9// L +10....L+14mArr[team] = getMedian(arr, teamFirst, Math.min(R, teamFirst + 4));}// marr中，找到中位数// marr(0, marr.len - 1,  mArr.length / 2 )return bfprt(mArr, 0, mArr.length - 1, mArr.length / 2);}public  int getMedian(int[] arr, int L, int R) {insertionSort(arr, L, R);return arr[(L + R) / 2];}public  void insertionSort(int[] arr, int L, int R) {for (int i = L + 1; i <= R; i++) {for (int j = i - 1; j >= L && arr[j] > arr[j + 1]; j--) {swap(arr, j, j + 1);}}}/*** 插入排序* @param arr* @return*/public  int[] copyArray(int[] arr) {int[] ans = new int[arr.length];for (int i = 0; i != ans.length; i++) {ans[i] = arr[i];}return ans;}/*** 交换* @param nums* @param i* @param j*/public void swap(int[]nums,int i,int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}

找出第K个最大元素

leetcode215. 数组中的第K个最大元素