欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

无序数组找第K大的数

程序员文章站 2024-03-15 22:52:15
...

1、使用HashMap或者Queue保存

如果是少量的数据,比如K=2,3等可以使用,如2,保存到HashMap找最大,合计为2N次比较。

2、典型解法:快速排序分组。

在数组中找到第k大的元素
取基准元素,将元素分为两个集合,一个集合元素比基准小,另一个比基准大 ,三种情况。
1.比基准大的元素数目标志位m正好为k-1,基准就是目的元素。
2.比基准大的元素标志位m小于k, 那么就在比基准小的集合里面找第(k-m)大的元素
3.若是比基准大的元素为m大于k,那就继续在该集合里面找第k大的元素。
如下是代码:

 static void findKMax(int[] arr, int left, int right, int k) {
        int temp = partition(arr, left, right);
        if (temp == k - 1) {
            System.out.println(arr[temp]);
        } else if (temp > k - 1) {
            findKMax(arr, left, temp - 1, k);
        } else {
            findKMax(arr, temp + 1, right, k - temp);
        }
    }

 static int partition(int[] arr, int left, int right) {
        int temp = arr[left];
        while (left < right) {
            while (temp >= arr[right] && left < right)
                --right;
            arr[left] = arr[right];
            while (temp <= arr[left] && left < right)
                ++left;
            arr[right] = arr[left];
        }

        arr[right] = temp;
        return right;
    }
    public static void main(String[] args) {
        int[] arr = new int[] { 12, 23, 2, 3, 2, 432, 43, 534, 5, 345, 3453, 53, 43 };
        findKMax(arr,0,arr.length - 1,2);
    }