3秒搞定！~~ 一億數據獲取前100個最大值

整合網絡上的算法。 根據我的思路。計算一億個數字中最大的前100個值。

昨晚效率還是很低。 今天搞的算法。 只需要3秒鐘。 獲取前100個 前1000個 速度都非常快。?

算法原理：

把一億個數字的前100個 首先放入數組。 然后把最小值放在ary[0]。

然后再，循環100到一億 之間的。 每次循環判斷當前數字是否大于ary[0]

?當大于時，當前數字放入ary[0] 并再次重構數組最小值進入ary[0]? 以此類推 。

當循環完這一億個數字后。 最大的前100個數字就出來了。

源碼分享地址：http://download.csdn.net/download/yjflinchong/4275241

騰訊面試題：一億數字獲取前100個最大的數字辦法

比較笨的辦法。效率有點低。 只是實現了功能。 期待牛人的算法。

我弄了個最佳方案 http://blog.csdn.net/yjflinchong/article/details/7533972??? 3秒就搞定了

一億數字獲取前100個最大的數字? 這個方案需要700秒

///http://blog.csdn.net/yjflinchong/article/details/7532018

package com.my.util;

import java.io.*;
import java.util.*;
import java.net.*;

public class WebTest {

?? ?public static int last = 333333333;
?? ?public static int max = 100000000;//數據總數
?? ?public static int sp = 1000000;//分割數據條數
?? ?public static int[] ary = new int[100];
?? ?
?? ?
?? ?public static void main(String[] args) {
?? ??? ?splitFile();
?? ??? ?Date d1 = new Date();
?? ??? ?find("d:/file/file.txt");
?? ??? ?System.out.println(Arrays.toString(ary)+"========");
?? ??? ?Date d2 = new Date();
?? ??? ?System.out.println(d2.getTime()-d1.getTime());
?? ?}
?? ?
?? ?
?? ?public static void splitFile(){
?? ??? ?StringBuffer str = new StringBuffer("");
?? ??? ?int num = 1;
?? ??? ?for (int i = 1; i < (max+1); i++) {
?? ??? ??? ?str.append(i+"\t\n");
?? ??? ??? ?if(i%1000000==0){
?? ??? ??? ??? ?appendToFile("d:/file/file.txt", str.toString());
?? ??? ??? ??? ?str = new StringBuffer("");
?? ??? ??? ??? ?num++;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?appendToFile("d:/file/file.txt", last+"");
?? ?}

?? ?public static void appendToFile(String file,String text){
?? ??? ?try
?? ??? ?{
?? ??? ??? ?FileWriter fw =new FileWriter(file,true);
?? ??? ??? ?BufferedWriter bw=new BufferedWriter(fw);
?? ??? ?bw.write(text);
?? ??? ?bw.flush();
?? ??? ?}catch (Exception e) {
?? ??? ?} ?
?? ??? }? ?
?? ??? ?public static String readFile(String path){
?? ??? ??? ? StringBuffer str = new StringBuffer("");
?? ??? ??? ?try {
?? ???????????? String line = null;
?? ?????????? ?
?? ???????????? BufferedReader reader = new BufferedReader(new FileReader(path));
?? ???????????? while ((line = reader.readLine()) != null) {
?? ??????????? ??? ?str.append(line);
?? ???????????? }
?? ???????????? reader.close();
?? ???????? } catch (Exception e) {
?? ???????????? e.printStackTrace();
?? ???????? }
?? ???????? return str.toString();
?? ??? ?}
?? ??? ?public static void find(int[] bak){
?? ??? ??? ?for (int i = 0; i < bak.length; i++) {
?? ??? ??? ??? ?ary[0] = bak[i];
?????????? ??? ?sort(ary);
?? ??? ??? ?}
?? ??? ?}///http://blog.csdn.net/yjflinchong/article/details/7532018
?? ??? ?public static void find(String path){
?? ??? ??? ?try {///http://blog.csdn.net/yjflinchong/
?? ???????????? String line = null;
?? ???????????? BufferedReader reader = new BufferedReader(new FileReader(path));
?? ???????????? while ((line = reader.readLine()) != null) {
?? ??????????? ??? ?ary[0] = Integer.parseInt(line.trim());
?? ??????????? ??? ?sort(ary);
?? ???????????? }
?? ???????????? reader.close();
?? ???????? } catch (Exception e) {
?? ???????????? e.printStackTrace();
?? ???????? }
?? ??? ?}
?? ??? ?///http://blog.csdn.net/yjflinchong/article/details/7532018
?? ??? ?public static void sort(int[] array){ ?
?? ???????? for(int i = 0; i < array.length - 1; i++){ ?
?? ???????????? //當前值當作最小值 ?
?? ???????????? int min = array[i]; ?
?? ???????????? for(int j = i+1; j < array.length; j++){ ?
?? ???????????????? if(min>array[j]){ ?
?? ???????????????????? //如果后面有比min值還小的就交換 ?
?? ???????????????????? min = array[j]; ?
?? ???????????????????? array[j] = array[i]; ?
?? ???????????????????? array[i] = min; ?
?? ???????????????? } ?
?? ???????????? } ?
?? ???????? } ?
?? ???? } ?
?? ??? ?
?? ??? ?

}

一億個數字判斷其中相同數字的辦法

一億個數字判斷其中相同數字的辦法

package com.my.util;

//http://blog.csdn.net/yjflinchong
public class Test {
?? ?
?? ?int fnum = 21000000;
?? ?
?? ?public static void main(String[] args) {
?? ??? ?Test t = new Test();
?? ??? ?t.find();
?? ?}
?? ?
?? ?
?? ?public void find() {
?? ??? ?int total = 100000000;
?? ??? ?int size = total%32==0?total/32:total/32+1;
?? ??? ?int [] mBits=new int[size];
?? ??? ?for(int i=0;i<total;i++) {
?? ??? ??? ?int num = getNum(i);
?? ??? ??? ?if(get(mBits,num)) {
?? ??? ??? ??? ?System.out.println(num);
?? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ??? ? ?? ?set1(mBits,num);
?? ??? ?}
?? ?}
?? ?//http://blog.csdn.net/yjflinchong
?? ?public int getNum(int i) {
?? ??? ?//設定模擬重復的那個數字 fnum
?? ??? ?if(i==(fnum+1)){
?? ??? ??? ?i--;
?? ??? ?}
?? ??? ?return i;
?? ?}
?? ?public void set1(int [] mBits, int pos) { ?
?? ??? ?int index = ( int )Math.floor(pos/32f);
?? ??? ?mBits[index] = mBits[index] | (1 <<(31-pos%32 ));
?? ?}
?? ?public boolean get(int [] mBits, int pos){ ?
?? ??? ?int index = ( int )Math.floor(pos/32f);
?? ??? ?return mBits[index] == (mBits[index] | 1 <<(31-pos% 32 ));
?? ? }

}