确定一组N个数中的第k个最大值,这是数据结构和算法分析(java语言描述)中讨论的第一个问题。书中第一章也已给处两种常规思路:
1-先将N个数的数组整体进行递减排序,然后返回位置k(数组索引为k-1)上的元素。
2 - 先将N个数的前k个数读入到数组,并将数组递减排序。然后将剩下的元素逐个读入。新元素读取时,如果小于数组中第k个元素则忽略,否则就放入到正确的位置,同时数组中最后一个元素被挤出数组。算法结束时,位于数组的第k个元素就是需要返回的答案。
实现方案1:
编写一个方法,实现对传入数组的递减排序并返回第k个值
public static int sortAndReturn(int k, int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - 1; j++) {
if (arr[j] < arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr[k - 1];
}
在main方法中对已有数组测试:
public static void main(String[] args) {
int[] arr = { 12, 23, 34, 45, 53, 98, 6, 68, 17, 80, 18, 29, 83, 59, 40 };
System.out.println(sortAndReturn(10, arr));
}
程序输出为29,排序后的数组为98 83 80 68 59 53 45 40 34 29 23 18 17 12 6 (可以在sortAndReturn方法中对已排序数组遍历输出观察),上面第十个最大值也为29,正确。
实现方案2:
先读入前K个元素到数组并递减排序,再用后面的新元素与数组元素对比根据比较结果将新元素放入数组中正确的位置或舍弃,算法结束时返回位置K上的元素
public static int readInAndReturn(int k, int[] arr) {
int[] newArr = new int[k];
for (int i = 0; i < newArr.length; i++) {
newArr[i] = arr[i];
}
for (int i = 0; i < newArr.length; i++) {
for (int j = i; j < newArr.length; j++) {
if (newArr[i] < newArr[j]) {
int temp=newArr[i];
newArr[i]=newArr[j];
newArr[j]=temp;
}
}
}
for (int i = k; i < arr.length; i++) {
int newElement=arr[i];
if (newElement > newArr[k - 1]) {
for (int j = 0; j < newArr.length - 1; j++) {
if (newArr[j] > newElement &&newElement > newArr[j + 1]) {
if (k>j+1) {
newArr[m]=newArr[m-1];
}
}
newArr[j+1]=newElement;
}
}
}
}
System.out.print("算法完成时的新数组");
for (int i = 0; i < newArr.length; i++) {
System.out.print(newArr[i]+" ");
}
System.out.println();
return newArr[k-1];
}
在main方法中测试运行:
public static void main(String[] args) {
int[] arr = { 12, 23, 34, 45, 53, 98, 6, 68, 17, 80, 18, 29, 83, 59, 40 };
System.out.println(readInAndReturn(10, arr));
}
程序运行得到输出:
算法完成时的新数组98 83 80 68 59 53 45 40 34 29
29
返回为29。与方案1一样。
这里完成了该问题的两种常规思路代码实现。对比两种方法,方案1的思路和代码都要稍简单,但是对于N是较大数据时,需要整体排序的方案1效率显然不够。而如果N足够大时,两种方法均不能在合理时间内解决。所以,这两种方法只适用于小数据范围的求解。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)