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