请高手来做个JAVA算法题

Question

[12,127,85,66,27,34,15,344,156,344,29,47,....]      
这是某设备测量到的工程数据。    
因工程要求，需要找出最大的5个值。    
一般的想法是对它排序，输出前5个。但当数据较多时，这样做很浪费时间。因为对输出数据以外的数据进行排序并非工程要求，即便是要输出的5个数字，也并不要求按大小顺序，只要找到5个就可以。    
以下的代码采用了另外的思路。考虑如果手里已经抓着5个最大数，再来一个数据怎么办呢？让它和手里的数据比，如果比哪个大，就抢占它的座位，让那个被挤出来的再自己找位子,....
import java.util.*;
public class B23
{
public static List<Integer> max5(List<Integer> lst)
{
if(lst.size()<=5) return lst;
int a = _______________________;  // 填空
List<Integer> b = max5(lst);
for(int i=0; i<b.size(); i++)
{
int t = b.get(i);
if(a>t)
{
__________________;  // 填空
a = t; 
}
}
return b;
}
public static void main(String[] args)
{
List<Integer> lst = new Vector<Integer>();
lst.addAll(Arrays.asList(12,127,85,66,27,34,15,344,156,344,29,47));
System.out.println(max5(lst));
}
}    请分析代码逻辑，并推测划线处的代码。

Answer 1

int a = lst.remove(0);
b.set(i, a);是这样吗？

Answer 2

int a = lst.remove(0);
b.set(i, a);
先取后5个数，跟前面去掉的数（a）比较，a大就把它放到b里，递归···

Answer 3

1L说对了
其实不用递归，递归只是为了得到最开始的只有5个数据的lst，而其用数组比lst快//非递归做法
public static int[] max5(List<Integer> lst)
{
    int count = Math.min(5, lst.size());
    int[] b = new int[count]; //当然也可以用list来做，但是用数组效率要好一些
    for (int i=0; i<count; i++) b[i] = lst.get(i); //相当于递归做法的获得b，
     //当然递归做法是获得lst的后5个元素，这里是前5个元素，获得后5个元素用lst.size()-count+i就可以了
    for (int i=count; i<lst.size(); i++) {
        int a = lst.get(i); //这里相当于1L的递归做法的 a = lst.remove(0);
        for (int j=0; j<count; j++) {
            if (a > result[j]) { //相当于交换a和b的某个位置的数据
                int t = result[j];
                b[j] = a; //这里就相当于1L的lst.set(i, a)
                a = t;
            }
        }
    }
    return b;
}

Answer 4

1L是对的
用数组的话会更快点import java.util.Arrays;public class MyTop {
static final int[] NUMS = new int[]{12,127,85,66,27,34,15,344,156,344,29,47};
static final int SIZE = 5;//前5个最大数
static int[] TOPS = new int[SIZE];//存放最大值的数组

public static void main(String[] args) {
long start = System.nanoTime();//开始
find(NUMS.length, SIZE);//获取最大数
System.out.println(Arrays.toString(TOPS));//打印
long end = System.nanoTime();//结束
System.out.println("time = " + (end - start) / 1e9 + " seconds");//输出时间
}

static void find(int total,int size){
//前5个数直接存入数组
for(int i = 0;i < size;++i){
TOPS[i] = NUMS[i];
}
setMin();
for(int i = size;i < total;++i){
//如果当前数比arr[0]大，将arr[0]替换为num,再获取最小值放入arr[0]
if(NUMS[i] > TOPS[0]){
TOPS[0] = NUMS[i];
setMin();
}
}
}

static void setMin(){
int min = TOPS[0];
int index = 0;
for(int i = 1;i < TOPS.length;i++){
if(TOPS[i] < min){
min = TOPS[i];
index = i;
}
}
int temp = TOPS[0];
TOPS[0] = TOPS[index];
TOPS[index] = temp;
}
}

Answer 5

/**
 * 取得数组中最大的子数组</br>
 * 在长数组中取得前N个值，作为最大的子数组，如果遇到后面的数比子数组中最小值小，则将此值设入子数组中
 */
public class MaxSubArray {
private int[] ints = null; private int count = 1; public MaxSubArray(int[] ints) {
this.ints = ints;
} public MaxSubArray(int[] ints, int count) {
this.ints = ints;
this.count = count;
} public int[] getMaxArray() {
int[] mis = new int[count];
System.arraycopy(ints, 0, mis, 0, count); Info info = min(mis);
for (int i = count; i < ints.length; i++) {
if (ints[i] > info.min) {
mis[info.point] = ints[i];
info = min(mis);
}
} Arrays.sort(mis);
return mis;
} private Info min(final int[] ints) {
Info info = new Info();
info.min = ints[0];
info.point = 0;
for (int i = 1; i < ints.length; i++) {
if (info.min > ints[i]) {
info.min = ints[i];
info.point = i;
}
}
return info;
} private class Info {
private int min;
private int point;
}
}
很早以前的代码

Answer 6

看例子代码的算法还不是最优的
这个时间复杂度是O(n*log(k)) k为前k大
用nth-element可以是做到 O(n);
感兴趣的话可以看看nth-element 其实就是快排的思想

Answer 7

1楼的不对
remove(0)的时间复杂度 是 n .（list 的特性）
如果remove(lst.size（）-1)的话，时间复杂度要小很多。
for(int i=0; i<b.size(); i++)这个可以写成
for(int i=0; i<5; i++) 就可以了