博客

确定一组N个数中的第k个最大值，这是数据结构和算法分析(java语言描述)中讨论的第一个问题。书中第一章也已给处两种常规思路：

1－先将N个数的数组整体进行递减排序，然后返回位置k(数组索引为k-1)上的元素。

2 – 先将N个数的前k个数读入到数组，并将数组递减排序。然后将剩下的元素逐个读入。新元素读取时，如果小于数组中第k个元素则忽略，否则就放入到正确的位置，同时数组中最后一个元素被挤出数组。算法结束时，位于数组的第k个元素就是需要返回的答案。

实现方案1：

编写一个方法，实现对传入数组的递减排序并返回第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 };

        // 采用方法1，输出数组arr中第十个最大值
        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) {

        // K个元素的新数组
        int[] newArr = new int[k];

        for (int i = 0; i < newArr.length; i++) {
            newArr[i] = arr[i];
        }
        // 选择排序实现新数组newArr的递减排序
        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];          

            // 新元素比newArr中的最小元素大才能进一步比较
            if (newElement > newArr[k - 1]) {

                for (int j = 0; j < newArr.length - 1; j++) {
        //如果新元素大小在两个元素之间  插入新元素，插入位置后的元素索引后移（元素位置后移1）
                    if (newArr[j] > newElement &&newElement > newArr[j + 1]) {

                        if (k>j+1) {
                    //数组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 };

        //采用方法2，数组arr中第十个最大值
        System.out.println(readInAndReturn(10, arr));
    }

程序运行得到输出：

算法完成时的新数组98 83 80 68 59 53 45 40 34 29

29

返回为29。与方案1一样。

这里完成了该问题的两种常规思路代码实现。对比两种方法，方案1的思路和代码都要稍简单，但是对于N是较大数据时，需要整体排序的方案1效率显然不够。而如果N足够大时，两种方法均不能在合理时间内解决。所以，这两种方法只适用于小数据范围的求解。