【算法】【数组与矩阵模块】求无序数组中前k个小的数

news/2024/4/25 23:38:09/文章来源:https://blog.csdn.net/qq_39760347/article/details/129132282

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定一个数组arr和一个正整数k，求arr的前k个小的数

解决方案

原问题：
堆解法：
维护一个长度为k的大根堆（如果求前k个小的值），堆如果没满则进入堆底并上浮，如果堆满了，则判断堆顶（当前最大值），比堆顶大则不需要入堆，比堆顶小，则将堆顶替换掉，进行一次下沉操作即可
时间复杂度：O（nlogn）
BFPRT算法：
该算法能够找到全局第k小的数，剩下只需要再遍历一次数组即可，该算法有以下几个步骤：
定义一个方法能够从当前数组arr中获取第k个小的值
1、将arr中n个元素划分成n/5组，每一组有5个元素，左右剩余不足5个元素的自成一组
2、将每组元素进行插入排序，并求出中位数，一共存在n/5+1或者n/5个中位数
3、将中位数组拿到后再次找到中位数的中位数，这次不再使用插排法或者而是递归使用定义的方法，换一种说法就是找到第len/2小的值也就是中位数
4、根据找到的中位数的中位数x，将数组进行一次快排划分，将小于x的放到左边，大于x的放到右边，等于的放到中间
5、判断x的位置范围（因为有可能存在与x相等的元素），如果k值再x范围中间，则直接返回x，x就是第k小的数，如果在左边，则左边继续进行递归找第k小的数，如果在右边，则右边继续递归找第 k-（x最右边的那个index）小的数.
6、找到之后再次遍历数组即可
时间复杂度：O(n)

代码编写

java语言版本

原问题：

    /*** 二轮测试：求arr中前k个小的数** @param arr* @return*/public static int[] printKMinCp1(int[] arr, int k) {if (arr == null || arr.length == 0 || k <= 0) {return null;}// 维护一个k大小的大根堆int[] res = new int[k];for (int i = 0; i < arr.length; i++) {if (i < k) {// 说明堆没有满heapInsertCp1(res, i, arr[i]);} else {// 说明堆满了,比较头节点if (arr[i] < res[0]) {// 替换顶res[0] = arr[i];// 进行一波下沉,因为这里堆已经满了，所以就不写通用的推下沉方法了，正常来说应该要给一个sizeheapify(res, 0);}}}return res;}/*** 从i处开始下城** @param res* @param i*/private static void heapify(int[] res, int i) {int size = res.length;// 申请内存int parent = i;int left = parent * 2 + 1;while (left < size) {// 先跟左节点比较出大值int maxIndex = res[parent] < res[left] ? left : parent;// 判断右节点是否存在，是否右节点更大int right = left + 1;if (right < size && res[right] > res[maxIndex]) {// parent需要和right交换maxIndex = right;}// 判断是否交换if (maxIndex == parent) {// 不用交换直接退出break;}// 需要交换CommonUtils.swap(res, parent, maxIndex);// 更新parent和leftparent = maxIndex;left = parent * 2 + 1;}}/*** 将value插入到arr的index处并进行一波上浮操作** @param res* @param index* @param value*/private static void heapInsertCp1(int[] res, int index, int value) {res[index] = value;int i = index;while (i != 0) {// 计算出父节点int parent = (i - 1) / 2;if (res[parent] < value) {// 交换CommonUtils.swap(res, parent, i);// 继续下一轮i = parent;} else {break;}}}public static void main(String[] args) {CommonUtils.printArr(printKMinCp2(new int[]{5, 3, 6, 1, 2, 7, 4}, 3));}

BFPRT算法：

/*** 二轮测试：方法2，BFPRT 算法求arr中前k个小的数** @param arr* @return*/public static int[] printKMinCp2(int[] arr, int k) {if (arr == null || arr.length == 0 || k <= 0) {return null;}// arr中第k小的数的位置int kMin = BFPRTCP2(arr, k);int[] res = new int[k];int index = 0;for (int i = 0; i < arr.length; i++) {if (index == k) {break;} else {if (arr[i] < kMin) {res[index++] = arr[i];}}}// 将剩下的多余位置都变成kminwhile (index < k) {res[index++] = kMin;}return res;}private static int BFPRTCP2(int[] arr, int k) {return selectCp1(arr, 0, arr.length - 1, k - 1);// 分数组// 各数组插入排序，选出中位数并组成一个新的arr// 求新的arr中第arr.lenth/2 小的数,即为midIndex// 重新调整数组，算出中间值mid的新位置// k==mid，返回，小于 求左边，大于求右边}/*** 递归主体** @param arr* @param start* @param end* @param k* @return*/private static int selectCp1(int[] arr, int start, int end, int k) {if (start == end) {return arr[start];}int mid = getMidOfMid(arr, start, end);int[] range = getRange(arr, start, end, mid);if (k >= range[0] && k <= range[1]) {return arr[k];} else if (k <= range[0]) {// 在左边return selectCp1(arr, 0, range[0] - 1, k);} else {// 在右边return selectCp1(arr, range[1] + 1, end, k - range[1]);}}private static int[] getRange(int[] arr, int start, int end, int mid) {// 两个边界int small = start - 1;int big = end + 1;int cur = start;while (cur < big) {if (arr[cur] < mid) {CommonUtils.swap(arr, ++small, cur++);} else if (arr[cur] > mid) {CommonUtils.swap(arr, cur, --big);} else {cur++;}}return new int[]{small + 1, big - 1};}/*** 获取中位数的中位数** @param arr* @param start* @param end* @return*/private static int getMidOfMid(int[] arr, int start, int end) {// 中位数个数计算int len = (end - start + 1) / 5 + ((end-start+1) % 5 == 0 ? 0 : 1);// 中位数容器int[] midArr = new int[len];for (int i = 0; i < midArr.length; i++) {// 循环计算中位数midArr[i] = getMid(arr, i * 5, i * 5 + 5 > end ? end : i * 5 + 4);}// 计算中位数的中位数return selectCp1(midArr, 0, midArr.length-1, midArr.length / 2);}/*** 获取midarr的中位数** @param midArr* @param start* @param end* @return*/private static int getMid(int[] midArr, int start, int end) {// 插入排序insertSortCp2(midArr, start, end);// 找到中位数,偶数为下中位数return midArr[(start + end) / 2 + ((end - start+1) % 2 == 0 ? 1 : 0)];}/*** 插入排序** @param midArr* @param start* @param end*/private static void insertSortCp2(int[] midArr, int start, int end) {for (int i = start; i <= end; i++) {for (int j = i; j > start; j--) {if (midArr[j] < midArr[j - 1]) {CommonUtils.swap(midArr, j, j - 1);} else {break;}}}}