LeetCode 215. Kth Largest Element in an Array

Description

https://leetcode.com/problems/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.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

Explanation

Use heap is easy to find k largest.

Python Solution

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return heapq.nlargest(k, nums)[-1]
  • Time complexity: O(N log(k)).
  • Space complexity: O(k).

3 Thoughts to “LeetCode 215. Kth Largest Element in an Array”

  1. /** java **/

    class Solution {

    public int findKthLargest(int[] nums, int k) {
    PriorityQueue q = new PriorityQueue();
    for(int i: nums){
    q.offer(i);
    if(q.size() > k) {
    q.poll();
    }
    }
    return q.peek();
    }

    // Another approach

    public int findKthLargest1(int[] nums, int k) {
    if(nums == null || nums.length == 0 ) return -1;
    int len = nums.length;

    Arrays.sort(nums);
    return nums[len-k];

    }

    }

Leave a Reply

Your email address will not be published. Required fields are marked *