专栏首页Coding迪斯尼在未知长度的超大数组中线性时间内查找第k大的元素

在未知长度的超大数组中线性时间内查找第k大的元素

给定一个长度为n的数组,n是一个很大的值,而且事先不知道n的大小,给定一个确定的数值k,要求设计一个找出数组中第k大的元素,要求算法需要的空间不能超过O(k)。

这个题目的处理有两个麻烦点,第一是它的总长度n不能提前知道,第二点在于题目对算法的空间有限定。对于找到第k小元素这类题目,一般的解法都是使用堆,例如我们先从数组中拿到k个元素,然后在k个元素上构造一个大堆,接着依次读入后续元素,如果读到的元素比大堆的根节点还要打,那么我们直接丢弃该元素,如果读到的元素比大堆根节点要小,那么我们去掉大堆根元素,然后把新元素加入堆。由于大堆能够始终把当前k个元素的最大值维持在根节点,因此当我们把数组中所有元素都遍历后,大堆根节点就是数组中第k大的元素。

根据我们前面对堆这种数据结构的研究,k个元素构造的大堆,其空间复杂度为 O(k),读取根节点的时间复杂度为O(1),插入一个新节点的时间复杂度为O(lgk),于是遍历完n个元素,算法的总时间复杂度为O(n*lg(k))。

有没有更好的方法呢?我们先把问题分解一下,假设给定一个含有n个元素的数组,n是确定的,那么怎么才能快速的在数组中找到第k大的元素?这里我们引入一种随机化的算法。我们随机在数组中取一个元素P,把所有小于P的元素放在它的左边,把所有大于P的元素放在它的右边。如果在随机选择中,正好选中了第k小的元素,那么P的左边就会有k-1个元素。如果选中元素比第k大元素小,那么左边元素就会少于k-1个,假设左边是t个元素,那么我们以同样的方法在右边元素中查找第k - t - 1大的元素就可以了。如果选择的元素比第k大的元素大,那么P左边元素的个数就会比k-1大,于是我们继续在左边元素中以同样的方法在P左边元素中继续查找第k大的元素。

问题在于,上面元素P是随机选择的,于是我们如何确定算法的时间复杂度?但算法涉及到随机性时,我们一般计算它的期望时间复杂度。我们用T(n)来表示上面算法的时间复杂度。由于是随机选择,那么数组中每个元素被选中的概率是一样的,于是某个元素被选中的几率是1/n,假设我们选中第t大的元素,那么数组就会被分成两部分,在元素的左边含有t-1个元素,在元素的右边含有n - t 个元素,我们设想一种最坏的情况是,我们要查找的元素每次都落在元素个数多的那部分,下面我们在数学上证明T(n)的期望值为O(n),不喜欢数学证明的同学可以忽略下面这部分,直接记住结论就可以。

我们随机选定一个元素P后,我们要把所有小于P的元素搬到它的左边,大于P的元素搬到它的右边,这个过程的时间复杂度是O(n)。然后我们到含有元素多的那部分继续运行同样的代码,于是我们就有:

这里我们引入一个随机变量X(i),当随机选择的元素是第i小时,X(i)=1,于是对于任意i处于1到n,P(X(i) = 1) = 1/n。那么上式子可以改写为:

两边取数学期望就有:

由数学期望的性质,和的数学期望等于数学期望的和,于是上面式子改写为:

然后数学期望里面相乘的两个变量如果是不相关,那么可以把它们拿出来,于是上面式子又变为:

其中E[Xi] = 1/n,上面式子再一步简化得到:

当i处于区间[1,n/2]时,T(max(i-1, n-i)) = T(n-i) = T(n),T(n-1)…T(n/2),当i处于区间[n/2+1,n]时,T(max(i-1, n-i)) = T(i-1) = T(n),T(n-1)…T(n/2),由此上面的式子继续简化为:

如果E[T(n)]=O(n),那意味着存在一个常数c使得E[T(n)] <= c*n,把前者代入上面公式就有:

O(n)意味着存在一个常数a,使得它等于an,于是把上面式子求和后化简就有:

只要cn/4 - c/2 - an > 0那么就能确定E[T(n))<=cn,我们只要c/4>a,这样随着n的增加,不等式一定成立,于是我们就证明,存在一个常数c,使得E[T(n)]<=c*n也就是E[T(n)] = O(n).

如果你对上面的数学推导不理解也无所谓,你只要记住,要想在n个元素中查找第k大的元素,先随机选择一个元素P,如果然后把比P小的元素搬到它左边,比它大的元素搬到它右边,如果P的前面有k-1个元素,那么P就算第k大的元素,如果不是再对应的到左边或右边元素间做同等操作,这种办法找到第k大元素的时间复杂度是O(n)。

有了上面的方法之后,我们如何完成题目的要求呢?我们可以申请一个2k长度的内存,每次从数组中读入元素时就存入2k内存,当把内存填满后,用上面方法找到第k大的元素,然后保留前k个元素,新读入的元素填充后k个单位的内存,每次2k内存填满后就使用上面方法查找第k大元素,直到n个元素全部读取完毕,此时2k内存中第k大的元素就是数组中第k大的元素。

由于每次在2k个元素中查找第k大的元素所需时间复杂度为O(2k),总的查找次数是 n/k,于是总的时间复杂度是O(2k)* n\k = O(n)。我们看看相应的代码实现:

import java.util.Random;

public class SearchKthElement {
    private int[] array = null; 
    private int elementPos = -1; 
    private int[] twoKBuffer = null;

    public SearchKthElement(int[] arr, int k) {
        if (arr.length < k) {
            throw new IllegalArgumentException("k can not bigger than the length of array!");
        }

        this.array = arr;
        this.elementPos = k;
        //分配2k缓冲区
        this.twoKBuffer = new int[2*k];

        streamElementFromArray();
    }

    private int  findElementInBuffer(int begin, int end, int k) {  
        if (k > end - begin) {
            System.out.println("begin : " + begin + " end: " + end + " k:" + k);
            throw new IllegalArgumentException("k in not in valid range");
        }

        //如果数组所有元素重复,那么返回其中任何一个元素
        int v = twoKBuffer[begin];
        int count = 0;
        for (int i = begin+1; i <= end; i++) {
            if (twoKBuffer[i] == v) {
                count++;
            }
        }
        if (count == end - begin ) {
            return twoKBuffer[0];
        }

        Random rand = new Random();
        int pos = begin + rand.nextInt(end+1 - begin);
        int P = twoKBuffer[pos];
        //把小于P的元素搬到左边,大于P的元素搬到右边
        int b = begin, e = end;
        int posOfP = -1;
        while (b < e) {
            if (twoKBuffer[b] < P ) {
                b++;
                continue;
            }


            int temp = twoKBuffer[b];
            twoKBuffer[b] = twoKBuffer[e];
            twoKBuffer[e] = temp;
            if (twoKBuffer[e] == P) {
                posOfP = e;
            }
            e--;
        }
        /*
         * b 和 e 交汇时他们指向的元素可能小于P,为了确保e指向的元素大于等于P,如果此时e指向的元素小于P,那么就要把e往后挪一位
         */
        if (twoKBuffer[e] < P) {
            e++;
        }

        /*
         * 把元素P放在左右两部分元素的分界线上,也就是数组形成如下形式:
         * |********|********|
         *    <P   P   >=P
         * 左边部分小于P,中间是元素P,右边是大于等于P的元素 
         */
        //把P的值放到位置e上
        if (posOfP != -1) {
            int temp = twoKBuffer[e];
            twoKBuffer[e] = twoKBuffer[posOfP];
            twoKBuffer[posOfP] = temp;
        }

        /*
         * 把P左右两边的元素分别打印出来,主要出于调试目的
         */
        System.out.println("Pivot is : " + P);
        System.out.println("first half:");
        for(int i = begin; i < e; i++) {
            System.out.print(" " + twoKBuffer[i]);
        }
        System.out.println("\nsecond half: ");
        for (int j = e; j <= end; j++) {
            System.out.print(" " + twoKBuffer[j]);
        }
        System.out.print("\n");


        if (e - begin == k) {
            //如果P前面包括它自己有k个元素,那么P在当前数组是第k大的元素
            return twoKBuffer[e];
        }

        if (e - 1 - begin >= k) {
            //如果P前面有多于k个元素,那么第k大的元素在P的左边部分
            return findElementInBuffer(begin, e - 1, k);
        } else {
            //如果P左边的元素有t个,t < k, 那么第k大的元素在P的右边,它是右边数组第k-t大的元素
            k = k - (e - begin);
            return findElementInBuffer(e, end, k);
        }
    }



    private void streamElementFromArray() {
        int start = 0;
        int n = 0;
        int count = 0;

        try {
            /*
             * 依次从大数组中读入元素,然后放入2k缓冲区,如果缓冲区被填满,那么查找缓冲区元素中第k大的元素
             */
             while (true) {
                 if (start + count == twoKBuffer.length) {
                     findElementInBuffer(0, twoKBuffer.length - 1, elementPos);
                     count = 0;
                     start = elementPos + 1;
                 }

                 twoKBuffer[start + count ] = array[n];
                 count++;
                 n++;
             }
        }catch (IndexOutOfBoundsException e) {
            findElementInBuffer(0, start + count - 1, elementPos);
        }
    }

    public int getKthElement() {
        return twoKBuffer[elementPos];
    }
}

上面代码的基本逻辑就是在数组中选取任意一个元素P,然后把数组分成两部分,左边元素都小于P,中间是元素P,右边是所有大于P的元素,如果左边元素个数大于k,那么第k大的元素在左边部分,要不然它在右边部分,如果左边数组元素个数为t,那么对k大的元素对应右边部分数组第k-t大的元素。

我们看看入口处代码:

public class Searching {
     public static void main(String[] args) {
        int n = 30;
        //构造一个含指定个元素的数组
        int[] arr = new int[n];
        Random rand = new Random();
        for (int i = 0; i < n; i++) {
            arr[i] = rand.nextInt(100);
        }


        int k = 8;
        SearchKthElement sk = new SearchKthElement(arr, k);
        System.out.println("The " + k + "th element in array from algorithm is :" + sk.getKthElement());

        Arrays.sort(arr);
        System.out.println("The " + k + "th element in array after sorting is : " + arr[k]);
     }
}

我们构造了一个含有30个元素的数组,元素取值在0到100之间,然后设置k等于8,也就是查找第8大的元素。我们先调用前面实现的逻辑查找给定元素,然后把数组排序后,再取出第k大的元素,如果两次获得元素一样,那表明我们代码的逻辑和实现是正确的,上面代码运行后结果如下:

从运行结果上看,代码的逻辑和实现确实是正确的。

本文分享自微信公众号 - Coding迪斯尼(gh_c9f933e7765d)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-07-31

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 面试算法:lg(k)时间查找两个排序数组合并后第k小的元素

    望月从良
  • 查找算法:在双重排序的数组中进行快速查找

    假设A是一个n\*n的二维数组。它的行和列都按照升序排列,给定一个数值x,设计一个有效算法,能快速在数组A中查找x是否存在。同时考虑一个算法效率的下界,也就是无...

    望月从良
  • 面试算法:在循环排序数组中快速查找第k小的值d

    望月从良
  • 我不知道你知不知道但前端NEXT知道的伪元素小技巧

    腾讯NEXT学位
  • jquery教程之查找筛选函数

    三、children 取得一个包含匹配的元素集合中每一个元素的所有子元素的元素集合。

    老雷PHP全栈开发
  • Pseudo elements伪元素与Pseudo classes伪类

    ::after用于描述处于css渲染层的一个伪元素,相当于选中元素的最后一个子元素,但这个元素与DOM节点无关,位于选择的元素之后,伪元素的内容用content...

    gojam
  • 使用jQuery筛选排除元素以修改指定标签的属性

    1、eq()    筛选指定索引号的元素 2、first()  筛选出第一个匹配的元素 3、last()   筛选出最后一个匹配的元素 4、hasClas...

    山河木马
  • 我不知道你知不知道我知道的伪元素小技巧

    伪元素能做什么?我们要他有何用?它能为我们解决什么问题?和其他的方法相比她有什么有点?我们为什么要使用它?

    sunseekers
  • 如何使用python进行web抓取?

    本文摘要自Web Scraping with Python – 2015 书籍下载地址:https://bitbucket.org/xurongzhong/py...

    CDA数据分析师
  • JavaWeb(八)JQuery

    jQuery 市场用得比较多两个框架: jQuery 比较适合做一些互联网 的应用(12306.com,蘑菇街,美丽说,聚美) extjs 比较适合做后台管理系...

    二十三年蝉

扫码关注云+社区

领取腾讯云代金券