寻找最大的K个数优化解法_JAVA_编程开发_程序员俱乐部

昨天我们说了寻找最大的K个数常规的两种解法，一种使用快速排序，另外一种是部分排序。今天我们介绍一种优化解法，
思想如下：在数组arr中我们进行一趟快速排序，选定key，把数组分为两部分a1,和a2。a1中的元素大于等于key，a2中的元素小于key。这样的话就会有两种可能，第一：a1中的元素个数小于K，所以a1中的元素加上K-a1.length个元素就是数组arr中最大的K个数。第二：a1中的元素个数大于或等于K，则返回a1中最大的K个数。这样不断递归就可以决绝这个问题。
先说说，一次快速排序。我们需要返回两个数组a1,a2,但是java不支持多参返回，所以我们用二维数组做为返回参数。具体代码如下： //          
public static int[][] getArr(int[] arr) {
if (arr == null || arr.length == 0) {
return null;
}
int[][] newArr = new int[2][];
int key = arr[0];
List<Integer> list1 = new ArrayList<Integer>(); //首先使用list存储数据
List<Integer> list2 = new ArrayList<Integer>();
for (int i=1; i<arr.length; i++) {
if (arr[i] >= key) {
list1.add(arr[i]);
} else {
list2.add(arr[i]);
}
}
if (list1.size() < list2.size()) { //是数据存储更加均匀
list1.add(key);
} else {
list2.add(key);
}
int[] a1 = new int[list1.size()];//创建新的数组
for (int i=0; i<list1.size(); i++) {//数组赋值
a1[i] = list1.get(i);
}
int[] a2 = new int[list2.size()];
for (int i=0; i<list2.size(); i++) {
a2[i] = list2.get(i);
}
newArr[0] = a1;//储存大于等于key的元素
newArr[1] = a2;//存储小于key的元素
return newArr;
}
接下来我们就要递归调用了，代码如下，我们在外部声明一个list用来存储符合的数据，声明如下：
static List<Integer> list = new ArrayList<Integer>();
public static void xunzhao(int[] arr, int k) {
if (arr == null || arr.length == 0 || k < 0) {
return;
}
if (arr.length <= k) {//数据比K小
for (int i=0; i<arr.length; i++) {
list.add(arr[i]); //存储数据
}
return;
}
int[][] newArr = getArr(arr);
if (newArr[0].length >= k) { //a1的元素个数大于K,
xunzhao(newArr[0], k); //继续分解
} else {
for (int i=0; i<newArr[0].length; i++) {
list.add(newArr[0][i]); //存储元素
}
xunzhao(newArr[1], k-newArr[0].length); //在a2中获取K-a1.length个元素
}
}
原帖和源码下载地址http://www.exceptionhelp.com/posts/540