java - 有一个算法问题想请教,给定一亿个数,如何用最快的方法取出其中最大的三个数。
迷茫
迷茫 2017-04-18 09:13:57
0
8
869

最近有一个java大神,是蚂蚁支付宝的哦,问了我这么一个问题。我的回答是先将数组分解成两百个小数组或者更多,在开两百个thread进行排序,取最大,然后对这两百个数进行排序,取前三。其实我的思路根本就没有涉及到算法层面,也只是暴力破解。其实这不是最好的做法,因为这样会严重的浪费资源,然后他的回答是堆排序。我的问题是堆排序是怎样实现的,最好用代码体现出来。

迷茫
迷茫

业精于勤,荒于嬉;行成于思,毁于随。

membalas semua (8)
PHPzhong

取前三为什么要排序?新开辟三个变量的空间保存中间结果就行了。

这种方法的复杂度是O(nk),n是数据总量,k是要获取的数据数量。排序无论是堆排还是快排都是O(nlogn)。当k小于log(2, 10 ** 8)时还是有优势的,太大了就退化成插入排序了。

    阿神

    有N(N>>10000)个整数,求出其中的前K个最大的数。(称作Top k算法问题)。由于(1)输入的大量数据;(2)只要前K个,对整个输入数据的保存和排序是相当的不可取的。可以利用数据结构的最小堆来处理该问题。

    最小堆,对于每个非叶子节点的数值,一定不大于孩子节点的数值。这样可用含有K个节点的最小堆来保存K个目前的最大值(当然根节点是其中的最小数值)。每次有数据输入的时候可以先与根节点比较。若不大于根节点,则舍弃;否则用新数值替换根节点数值。并进行最小堆的调整。

    由于仅仅保存了K个数据,有调整最小堆的时间复杂度为O(logK),因此TOp K算法(问题)时间复杂度为O(nlogK).

      Ty80

      随手一搜
      http://www.cnblogs.com/skywang12345/p/3610187.html

      证明及推导参见算法导论

      但是可以不用堆吧,毕竟只找3个数……

        黄舟

        这不是典型的Top k问题吗,你可以百度一下Top K

          大家讲道理

          topn的如果说稳妥的答案堆排是没有错的 问题是这个3取的。。。这么小的数

            黄舟

            就是堆排序a

              Peter_Zhu

              topk求解

                黄舟

                如果想要最快,我觉得位图排序是我见过的最快的了。

                  Muat turun terkini
                  Lagi>
                  kesan web
                  Kod sumber laman web
                  Bahan laman web
                  Templat hujung hadapan
                  Tentang kita Penafian Sitemap
                  Laman web PHP Cina:Latihan PHP dalam talian kebajikan awam,Bantu pelajar PHP berkembang dengan cepat!