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

在未排序的数组中找到第 k 个最大的元素

程序员文章站 2022-03-23 11:29:42
一、引言昨儿面试中遇到的算法题 :在未排序的数组中找到第 k 个最大的元素。首先想到的就是先排序,但是就算是快排的时间复杂度也要O(nlogn),给的时间有限,一时间也没想出更好的办法,想着既然时间复杂度降不下来,那不如就用简单点的堆排序: //大根堆 O(nlogk) public int findKthLargest(int[] nums, int k){ PriorityQueue maxHeap = new PriorityQueue...

一、引言

昨儿面试中遇到的算法题 :在未排序的数组中找到第 k 个最大的元素。首先想到的就是先排序,但是就算是快排的时间复杂度也要O(nlogn),给的时间有限,一时间也没想出更好的办法,想着既然时间复杂度降不下来,那不如就用简单点的堆排序:

   //大根堆 O(nlogk)
    public int findKthLargest(int[] nums, int k){
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((n1, n2) -> n1-n2);
        for (int n: nums){
            maxHeap.add(n);
            if (maxHeap.size()>k){
                maxHeap.poll();
            }
        }
        return maxHeap.poll();
    }

结果显然,面试官不是很满意,最后给的建议也是说算法有点弱,确实最近忙着实习,算法题没怎么刷,生疏了。所以趁热打铁,反思的同时,这道题的较优解还是很巧妙的,特此记录。


二、正文

基于快速排序的选择方法
  1. 思路:

快速排序,是一个典型的分治算法
通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

结合快排,对子数组进行划分,如果划分得到的值正好就是我们需要的下标,就直接返回a[q];否则,如果 q 比目标下标小,就递归右子区间,否则递归左子区间。这样就可以把原来递归两个区间变成只递归一个区间,提高了时间效率。这就是「快速选择」算法。

  1. 代码:
	Random random = new Random();
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;

        // 转换一下,第 k 大元素的索引是 len - k
        int target = len - k;
        while (true) {
            //int i = random.nextInt(right - left + 1) + l;
            //swap(a, i, r);
            int index = partition(nums, left, right);
            if (index == target) {
                return nums[index];
            } else if (index < target) {
                left = index + 1;
            } else {
                right = index - 1;
            }
        }
    }
    //辅助函数,把比轴值大的元素放右边,比轴值小的元素放左边,返回轴值下标
    public int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        int j = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < pivot) {
                // 小于 pivot 的元素都被交换到前面
                j++;
                swap(nums, j, i);
            }
        }
        // 在之前遍历的过程中,满足 [left + 1, j] < pivot,并且 (j, i] >= pivot
        swap(nums, j, left);
        // 交换以后 [left, j - 1] < pivot, nums[j] = pivot, [j + 1, right] >= pivot
        return j;
    }
    
    //交换
    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

时间复杂度:O(N),这里 N 是数组的长度,需要使用主定理进行分析。
空间复杂度:O(1),原地排序,没有借助额外的辅助空间。
另外,为了应对极端测试用例,随机初始化 pivot 元素,随机交换第 1个元素与它后面的任意 1 个元素的位置;最极端的是顺序数组与倒序数组,此时递归树画出来是链表,时间复杂度是 O(N^2),根本达不到减治的效果。

本文地址:https://blog.csdn.net/qq_44543551/article/details/107327322