如何在无序数组中查找第K小的值

如题:给定一个无序数组,如何查找第K小的值。

例子如下:

在一个无序数组,查找 k = 3 小的数

 输入:arr[] = {7, 10, 4, 3, 20, 15} 输出:7

在一个无序数组,查找 k = 4 小的数

 输入:arr[] = {7, 10, 4, 3, 20, 15} 输出:10

几种思路如下和复杂度分析如下:

(1)最简单的思路直接使用快排,堆排或者归并排,排序之后取数组的k-1索引的值即可,时间复杂度为O(nLogn)

(2)用大小为k的数组存前k个数,然后找出这里面最大的值kmax,耗时O(K), 遍历剩余的数,如果有小于里面最大的数,就放进去替换掉当前最大的,依次遍历至结束,每次比较前都得找出kmax,故总的时间复杂度为:O(NK)

(3)使用大顶堆,初始化为k个值,然后后面从k+1开始,依次读取每个值,判断当前的值是否比堆顶的值小,如果小就移除堆顶的值,新增这个小的值,依次处理完整个数组,取堆顶的值就得到第k小的值。 时间复杂度为:建堆的时间为O(K),每次调整最大堆结构时间为O(lgK),从而总的时间复杂度为O(K + (N-K)lgK)(适合大数据量)

(4)利用快排找基准的原理,可以在平均时间复杂度O(N)级别完成,当然最坏的情况下是O(n2)与快排的最坏情况一样,但由于平均是O(N)的时间复杂度,所以这种方式一般认为是最优的解法。

原理如下: 根据题目描述,如果是第k小的值,那就说明在升序排序后,这个值一定在数组的k-1的下标处,如果在k-1处,也就是说只要找到像这样的左边有k个数比k小(可以是无序的,只要小就可以了),那么这个下标的值,就是我们要找的值,利用这个思想我们就可以使用快排的思想,来快速的找基准值的index(数组下标从0开始),如果恰好碰到了基准值的下标index+1=k,那就说明基准值index所在下标的值,就是我们要找的结果。

下面的代码就是基于第四种思路来实现的,其他的方式,有兴趣的可以自己研究一下。

注意,如果思路理解了,那么该题目的变形也比较容易处理,比如

(1)如给定一个无序数组,查找最小/大的k个数,或者叫前k小/大的所有数。

剖析:思路是一样,只不过在最后返回的时候,要把k左边的所有的数返回即可。

(2)给定一个大小为n数组,如果已知这个数组中,有一个数字的数量超过了一半,如何才能快速找到该数字?

剖析:有一个数字的数量超过了一半,隐含的条件是在数组排过序后,中位数字就是n/2的下标,这个index的值必定是该数,所以就变成了查找数组第n/2的index的值,就可以利用快排分区找基准的思想,来快速求出。当然这只是解法的一种。

下面我们看下,从无序数组,如何查找第K小的值,也就是按照上面第四种思路,实现的代码如下:

public class KthSmallest {
    public static  int quickSortFindRaidx(int a[],int left ,int right){
        int pivot=a[left];        int i=left;        int j=right;
        while (i!=j){            //找右边第一个小于基准点的数字            while (a[j]>=pivot&&i<j) j--;            //做右边第一个大于基准点的数字            while (a[i]<=pivot&&i<j) i++;
            if(i<j){//进行交换                int temp=a[i];                a[i]=a[j];                a[j]=temp;            }
        }        //基准归位        a[left]=a[i];        a[i]=pivot;
        return i;    }



    public static int findKthSmall(int a[], int left, int right , int k){            if(k<=0||k>a.length){                return -1;//超出查询范围,直接返回-1            }            //返回基准点的下标,从0开始            int pivotIndex = quickSortFindRaidx(a, left, right);            //包含基准点在内的左边的数字个数            int leftNumCount = pivotIndex + 1;
            //说明当前基准下标的值就是我们要找的            if (leftNumCount == k) {                return a[pivotIndex];            }            //说明要找的数,在基准点的左边,继续在左边部分递归查找            if (leftNumCount > k) {                return findKthSmall(a, left, pivotIndex, k);            }else {//说明要找的数,在基准点的右边,继续在右边部分递归查找                return findKthSmall(a, pivotIndex + 1, right, k);
            }
    }

    public static void main(String[] args) {
        int [] arr={12, 3, 5, 7, 4, 19, 26};        int kthMin = findKthSmall(arr,0,arr.length-1,1);
        System.out.println(kthMin);
    }
}

原文发布于微信公众号 - 我是攻城师(woshigcs)

原文发表时间:2019-05-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券