日期:2014-05-20  浏览次数:20546 次

请高手来做个JAVA算法题
[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));
}
} 请分析代码逻辑,并推测划线处的代码。

------解决方案--------------------
int a = lst.remove(0);
b.set(i, a);

是这样吗?
------解决方案--------------------
int a = lst.remove(0);
b.set(i, a);
先取后5个数,跟前面去掉的数(a)比较,a大就把它放到b里,递归···
------解决方案--------------------
1L说对了
其实不用递归,递归只是为了得到最开始的只有5个数据的lst,而其用数组比lst快

//非递归做法
Java code
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;
}

------解决方案--------------------
1L是对的
用数组的话会更快点
Java code

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;
    }
}

------解决方案--------------------
Java code

/**
 * 取得数组中最大的子数组</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;
    }
}