转载

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.

难度：medium

题目：找出在没有排序的数组中第K大的元素，注意是排序后的第K大的元素，不是第Ｋ个不同元素。

思路：快速排序

Runtime: 29 ms, faster than 36.08% of Java online submissions for Kth Largest Element in an Array.

Memory Usage: 38.8 MB, less than 51.09% of Java online submissions for Kth Largest Element in an Array.

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int idx = -1;
        k = nums.length - k;
        for (int i = 0, j = nums.length - 1; i <= j && idx != k;) {
            idx = quickSort(nums, i, j);
            if (idx < k) {
                i = idx + 1;
            } else if (idx > k) {
                j = idx - 1;
            }
        }
        
        return nums[idx];
    }
    
    private int quickSort(int[] nums, int i, int j) {
        int piovt = nums[i];
        while (i < j) {
            while (i < j && nums[j] >= piovt) {
                j--;
            }
            nums[i] = nums[j];
            while (i < j && nums[i] < piovt) {
                i++;
            }
            nums[j] = nums[i];
        }
        nums[i] = piovt;
        
        return i;
    }
}

原文 https://segmentfault.com/a/1190000018225730

正文到此结束