215. 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.

Language: Java

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        int p = quickSelect(nums, 0, n - 1, n - k + 1);
        return nums[p];
    }
    
    int quickSelect(int nums[], int left, int right, int k){
        if (left < right) {
            int i = left, j = right, pivot = nums[left];
            while (left < right) {
                while (left < right && nums[right] >= pivot) {
                    right--;
                }
                nums[left] = nums[right];
                while (left < right && nums[left] <= pivot) {
                    left++;
                }
                nums[right] = nums[left];
            }
            nums[left] = pivot;

            if (left + 1 == k) {
                return left;
            } else if (left + 1 > k) {
                return quickSelect(nums, i, left - 1, k);
            } else {
                return quickSelect(nums, right + 1, j, k);
            }
        }
        return left;
    }
    
}

Analysis:

  1. Minimum heap
  2. Quick sort

Submission Detail

Accepted Solutions Runtime Distribution

Accepted Solutions Memory Distribution

Language: Python

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        
        def partition(nums, l, r):
            i = l - 1
            pivot = nums[r]
            
            for j in range(l, r):
                if nums[j] >= pivot:
                    i += 1
                    nums[i], nums[j] = nums[j], nums[i]
            nums[i + 1], nums[r] = nums[r], nums[i + 1]
            return i + 1
        
        l = 0
        r = len(nums) - 1
        while True:
            pivot_index = partition(nums, l, r)
            if pivot_index == k - 1:
                return nums[k - 1]
            elif pivot_index > k - 1:
                r = pivot_index - 1
            else:
                l = pivot_index + 1

Submission Detail

Accepted Solutions Runtime Distribution

Accepted Solutions Memory Distribution

Summary:

  1. Java runtime is shorter than Python;
  2. Java uses more memory than Python;
  3. Python runtime is horrible;
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容