[Leetcode] Kth Largest Element in an Array 数组中第K大元

Rocko 发布于2019-08-14 12:26 / 304人阅读

摘要：优先队列复杂度时间空间思路遍历数组时将数字加入优先队列堆，一旦堆的大小大于就将堆顶元素去除，确保堆的大小为。如果这个分界点是，说明分界点的数就是第个数。

Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example, Given [3,2,1,5,6,4] and k = 2, return 5.
Note:  You may assume k is always valid, 1 ≤ k ≤ array"s length.

优先队列 复杂度

时间 O(NlogK) 空间 O(K)

思路

遍历数组时将数字加入优先队列（堆），一旦堆的大小大于k就将堆顶元素去除，确保堆的大小为k。遍历完后堆顶就是返回值。

代码

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue p = new PriorityQueue();
        for(int i = 0 ; i < nums.length; i++){
            p.add(nums[i]);
            if(p.size()>k) p.poll();
        }
        return p.poll();
    }
}

排序法 复杂度

时间 O(NlogN) 空间 O(1)

思路

将数组排序后，返回第k个元素。

代码

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

快速选择 Quick Select 复杂度

时间 Avg O(N) Worst O(N^2) 空间 O(1)

思路

跟快速排序一个思路。先取一个枢纽值，将数组中小于枢纽值的放在左边，大于枢纽值的放在右边，具体方法是用左右两个指针，如果他们小于枢纽值则将他们换到对面，一轮过后记得将枢纽值赋回分界点。如果这个分界点是k，说明分界点的数就是第k个数。否则，如果分界点大于k，则在左半边做同样的搜索。如果分界点小于k，则在右半边做同样的搜索。

注意

helper函数的k是k-1，因为我们下标从0开始的，我们要比较k和下标，来确定是否左半部分有k个数字。

互换左右时，也要先判断left <= right

代码

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, k - 1, 0, nums.length - 1);
    }
    
    private int quickSelect(int[] arr, int k, int left, int right){
        int pivot = arr[(left + right) / 2];
        int orgL = left, orgR = right;
        while(left <= right){
            // 从右向左找到第一个小于枢纽值的数
            while(arr[left] > pivot){
                left ++;
            }
            // 从左向右找到第一个大于枢纽值的数
            while(arr[right] < pivot){
                right --;
            }
            // 将两个数互换
            if(left <= right){
                swap(arr, left, right);
                left ++;
                right --;
            }
        }
        // 最后退出的情况应该是右指针在左指针左边一格
        // 这时如果右指针还大于等于k，说明kth在左半边
        if(orgL < right && k <= right) return quickSelect(arr, k, orgL, right);
        // 这时如果左指针还小于等于k，说明kth在右半边
        if(left < orgR && k >= left) return quickSelect(arr, k, left, orgR);
        return arr[k];
    
    }
    
    private void swap(int[] arr, int idx1, int idx2){
        int tmp = arr[idx1] + arr[idx2];
        arr[idx1] = tmp - arr[idx1];
        arr[idx2] = tmp - arr[idx2];
    
    }
}

GPU云服务器云服务器 js判定数组中第几个 in_array() in_array in_array()函数

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64481.html

Kth Largest Element in an Array，Top K Frequent Ele

摘要：解题思路，默认就是队列顶端是最小元素，第大元素，我们只要限制的大小为即可，最后队列顶端的就是第大元素。代码解题思路利用存入，之后采用，并限制最多放个元素。 Kth Largest Element in an ArrayFind the kth largest element in an unsorted array. Note that it is the kth largest el...

Tony_Zby 2019-08-16 10:27 评论0 收藏0
[LintCode] Kth Largest Element [PriorityQueue]

摘要：可以不要用太简单的方法。先把它装满，再和队列顶端的数字比较，大的就替换掉，小的就。遍历完所有元素之后，顶部的数就是第大的数。 Problem Find K-th largest element in an array. Example In array [9,3,2,4,8], the 3rd largest element is 4.In array [1,2,3,4,5], the...

Hwg 2019-08-14 15:12 评论0 收藏0
leetcode378. Kth Smallest Element in a Sorted Matr

摘要：因此我们可以采用部分元素堆排序即可。即我们每次只需要可能构成第个元素的值进行堆排序就可以了。题目要求 Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix. Note that...

dailybird 2019-08-16 15:05 评论0 收藏0
[Leetcode] Kth Smallest Element in a BST 二叉搜索树第k小节

摘要：中序遍历复杂度时间空间思路因为左节点小于根节点小于右节点，二叉搜索树的一个特性就是中序遍历的结果就是树内节点从小到大顺序输出的结果。这里采用迭代形式，我们就可以在找到第小节点时马上退出。这样我们就可以用二叉树搜索的方法来解决这个问题了。 Kth Smallest Element in a BST Given a binary search tree, write a function...

Dean 2019-08-14 12:26 评论0 收藏0
[LeetCode] 378. Kth Smallest Element in a Sorted M

摘要：先放一行，或一列把堆顶的最小元素取出来，取次，如果该有下一行下一列的，放入堆中最小的个元素已经在上面的循环被完了，下一个堆顶元素就是 Problem Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in...

Shihira 2019-08-16 13:43 评论0 收藏0