java寻找最大数_寻找最大的K个数优化解法

寻找最大的K个数优化解法

2014/4/11 9:48:24  exceptionhelp  程序员俱乐部  我要评论(0)

摘要：昨天我们说了寻找最大的K个数常规的两种解法，一种使用快速排序，另外一种是部分排序。今天我们介绍一种优化解法，思想如下：在数组arr中我们进行一趟快速排序，选定key，把数组分为两部分a1,和a2。a1中的元素大于等于key，a2中的元素小于key。这样的话就会有两种可能，第一：a1中的元素个数小于K，所以a1中的元素加上K-a1.length个元素就是数组arr中最大的K个数。第二：a1中的元素个数大于或等于K，则返回a1中最大的K个数。这样不断递归就可以决绝这个问题。先说说，一次快速排序

标签：优化

昨天我们说了寻找最大的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 list1 = new ArrayList(); //首先使用list存储数据

List list2 = new ArrayList();

for (int i=1; 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

a1[i] = list1.get(i);

}

int[] a2 = new int[list2.size()];

for (int i=0; i

a2[i] = list2.get(i);

}

newArr[0] = a1;//储存大于等于key的元素

newArr[1] = a2;//存储小于key的元素

return newArr;

}

接下来我们就要递归调用了，代码如下，我们在外部声明一个list用来存储符合的数据，声明如下：

static List list = new ArrayList();

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

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

list.add(newArr[0][i]); //存储元素

}

xunzhao(newArr[1], k-newArr[0].length); //在a2中获取K-a1.length个元素

}

}

原帖和源码下载地址http://www.exceptionhelp.com/posts/540