有一个算法问题想请教,给定一亿个数,如何用最快的方法取出其中最大的三个数。

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

BIG阳
浏览 722回答 8
8回答

30秒到达战场

有N(N>>10000)个整数,求出其中的前K个最大的数。(称作Top k算法问题)。由于(1)输入的大量数据;(2)只要前K个,对整个输入数据的保存和排序是相当的不可取的。可以利用数据结构的最小堆来处理该问题。最小堆,对于每个非叶子节点的数值,一定不大于孩子节点的数值。这样可用含有K个节点的最小堆来保存K个目前的最大值(当然根节点是其中的最小数值)。每次有数据输入的时候可以先与根节点比较。若不大于根节点,则舍弃;否则用新数值替换根节点数值。并进行最小堆的调整。由于仅仅保存了K个数据,有调整最小堆的时间复杂度为O(logK),因此TOp K算法(问题)时间复杂度为O(nlogK).

慕后森

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

Smart猫小萌

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

互换的青春

就是堆排序a

慕神8447489

topk求解

哔哔one

你要的堆排,JAVApublic class 堆排 {&nbsp; &nbsp; public static void main(String[] args) {&nbsp; &nbsp; &nbsp; &nbsp; int [] arr= {0,5,3,2,6,7};&nbsp; &nbsp; &nbsp; &nbsp; HeapSort(arr);&nbsp; &nbsp; &nbsp; &nbsp; for(int s:arr){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println(s);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; public static void BuildHeap(int[] arr,int s,int length){&nbsp; &nbsp; &nbsp; &nbsp; int temp = arr[s];&nbsp; &nbsp; &nbsp; &nbsp; for(int j = s*2 +1 ; j<length;j = j*2 +1){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(j+1<length && arr[j]>arr[j+1]){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(temp < arr[j]){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr[s] = arr[j];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; s = j;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; arr[s] = temp;&nbsp; &nbsp; }&nbsp; &nbsp; public static void HeapSort(int[] arr){&nbsp; &nbsp; &nbsp; &nbsp; for(int i = (arr.length)/2-1;i>=0;i--){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; BuildHeap(arr, i, arr.length);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; for(int i = arr.length - 1;i>=0;i--){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(arr[0]!= arr[i]){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr[i] ^= arr[0];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr[0] ^= arr[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr[i] ^= arr[0];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; BuildHeap(arr, 0, i);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}
打开App,查看更多内容
随时随地看视频慕课网APP

相关分类

Java