?

1.排序方法

首先能想到的就是先排序，然后取前1000個(gè)數(shù)，或者部分排序，只排出前1000個(gè)數(shù)就行

缺點(diǎn)：這些方法的時(shí)間復(fù)雜度都比較高

2，分治法

可以使用分治法，這有點(diǎn)類似快排中partition的操作，隨機(jī)選一個(gè)數(shù)t，然后對整個(gè)數(shù)組進(jìn)行partition，會(huì)得到兩部分，前一部分的數(shù)都大于t，后一部分的數(shù)都小于t。

如果說前一部分總數(shù)大于1000個(gè)，那就繼續(xù)在前一部分進(jìn)行partition尋找。如果前一部分的數(shù)小于1000個(gè)，那就在后一部分再進(jìn)行partition，尋找剩下的數(shù)。

首先，partition的過程，時(shí)間是o(n)。我們在進(jìn)行第一次partition的時(shí)候需要花費(fèi)n，第二次partition的時(shí)候，數(shù)據(jù)量減半了，所以只要花費(fèi)n/2，同理第三次的時(shí)候只要花費(fèi)n/4，以此類推。而n+n/2+n/4+...顯然是小于2n的，所以這個(gè)方法的漸進(jìn)時(shí)間只有o(n)

3.可以用分布式思想，將數(shù)據(jù)切分，然后在多臺機(jī)器上分別計(jì)算前1000大的數(shù)，最后再把這些數(shù)匯總

4.堆排序法（推薦）

如果只有一臺機(jī)器，可以在內(nèi)存中維護(hù)一個(gè)1000數(shù)的小頂堆，根據(jù)堆得性質(zhì)，每一個(gè)節(jié)點(diǎn)都比它的左右子節(jié)點(diǎn)要小

1.先去前N個(gè)數(shù)，構(gòu)成小頂堆

2.然后從文件中讀取數(shù)據(jù)，并且和堆頂大小相比，如果比對頂還小，就直接丟棄

3.如果比堆頂大，就替換堆頂，并調(diào)整最小堆

TopN.java

/*** @author xiaoshi on 2018/10/14.*/ public class TopN {// 父節(jié)點(diǎn)private int parent(int n) {return (n - 1) / 2;}// 左孩子private int left(int n) {return 2 * n + 1;}// 右孩子private int right(int n) {return 2 * n + 2;}// 構(gòu)建堆private void buildHeap(int n, int[] data) {for(int i = 1; i < n; i++) {int t = i;// 調(diào)整堆while(t != 0 && data[parent(t)] > data[t]) {int temp = data[t];data[t] = data[parent(t)];data[parent(t)] = temp;t = parent(t);}}}// 調(diào)整data[i]private void adjust(int i, int n, int[] data) {if(data[i] <= data[0]) {return;}// 置換堆頂int temp = data[i];data[i] = data[0];data[0] = temp;// 調(diào)整堆頂int t = 0;while( (left(t) < n && data[t] > data[left(t)])|| (right(t) < n && data[t] > data[right(t)]) ) {if(right(t) < n && data[right(t)] < data[left(t)]) {// 右孩子更小，置換右孩子temp = data[t];data[t] = data[right(t)];data[right(t)] = temp;t = right(t);} else {// 否則置換左孩子temp = data[t];data[t] = data[left(t)];data[left(t)] = temp;t = left(t);}}}// 尋找topN，該方法改變data，將topN排到最前面public void findTopN(int n, int[] data) {// 先構(gòu)建n個(gè)數(shù)的小頂堆buildHeap(n, data);// n往后的數(shù)進(jìn)行調(diào)整for(int i = n; i < data.length; i++) {adjust(i, n, data);}}// 打印數(shù)組public void print(int[] data) {for(int i = 0; i < data.length; i++) {System.out.print(data[i] + " ");}System.out.println();}}

Main.java

import java.util.Random;/*** @author xiaoshi on 2018/10/14.*/ public class Main {public static void main(String[] args) {TopN topN = new TopN();// 第一組測試int[] arr1 = new int[]{56, 30, 71, 18, 29, 93, 44, 75, 20, 65, 68, 34};System.out.println("原數(shù)組：");topN.print(arr1);topN.findTopN(5, arr1);System.out.println("調(diào)整后數(shù)組：");topN.print(arr1);// 第二組測試int[] arr2 = new int[1000];for(int i=0; i<arr2.length; i++) {arr2[i] = i + 1;}System.out.println("原數(shù)組：");topN.print(arr2);topN.findTopN(50, arr2);System.out.println("調(diào)整后數(shù)組：");topN.print(arr2);// 第三組測試Random random =new Random();int[] arr3 = new int[1000];for(int i=0; i<arr3.length; i++) {arr3[i] = random.nextInt();}System.out.println("原數(shù)組：");topN.print(arr3);topN.findTopN(50, arr3);System.out.println("調(diào)整后數(shù)組：");topN.print(arr3);}}

運(yùn)行結(jié)果：

原數(shù)組： 56 30 71 18 29 93 44 75 20 65 68 34 調(diào)整后數(shù)組： 65 68 71 75 93 18 29 30 20 44 56 34 原數(shù)組： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 調(diào)整后數(shù)組： 951 952 955 954 953 956 957 963 968 964 972 961 979 959 958 967 966 969 974 965 970 973 988 962 983 993 986 981 987 992 960 976 1000 982 978 977 975 985 984 990 971 997 996 991 989 999 998 980 994 995 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 原數(shù)組： 835636999 -90522479 -769818338 -1416245398 1041573706 1812203535 896607110 1789246766 1774883884 26722194 -418633859 1344767118 1570967674 1316806558 -1435502178 1473470755 -918439629 1869702742 2101404773 -1296472335 649689400 1153902366 -1052670714 498645159 -1530905537 -1159220094 -154125959 -868393434 -504505075 -1106082731 -494609447 -1406763201 -750828828 -342445539 -744595730 -1920006464 -1230413255 -1426324562 -1277878264 474935729 -2029054806 447026196 -1121975794 -1448358181 1957166126 1336854710 …… 調(diào)整后數(shù)組： 1960093727 1964906931 1970688292 1975808864 1981745799 1991241336 2022661667 1981095418 1998580270 1988169309 2008783098 2027208746 2136972032 2062185334 2058314391 2003774732 2022245178 2022674254 2076406457 2024695646 2106449320 2016192325 2039153729 2043057170 2042482994 2138695524 2139809413 2121618159 2067898415 2122335504 2101895240 2100462015 2054036800 2037921932 2067998974 2117710597 2133594097 2101404773 2077564852 2033907579 2035097590 2108250457 2122256662 2138496647 2088084171 2107415856 2077919162 ……

?

劃船不用槳、楊帆不等風(fēng)、一生全靠浪

轉(zhuǎn)載于:https://www.cnblogs.com/williamjie/p/11195186.html

總結(jié)

以上是生活随笔為你收集整理的如何在10亿数中找出前1000大的数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。