题目描述：

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.

题目大意：

从一个未经排序的数组中找出第k大的元素。注意是排序之后的第k大，而非第k个不重复的元素

测试样例如题目描述

可以假设k一定是有效的， 1 ≤ k ≤ 数组长度

解题思路：

O(n)解法：快速选择（QuickSelect）算法，参考耶鲁大学关于QuickSelect算法的介绍

O(nlogn)解法：排序

Python代码：

O(n)解法：快速选择算法

import random
class Solution:
    # @param {integer[]} nums
    # @param {integer} k
    # @return {integer}
    def findKthLargest(self, nums, k):
        pivot = random.choice(nums)
        nums1, nums2 = [], []
        for num in nums:
            if num > pivot:
                nums1.append(num)
            elif num < pivot:
                nums2.append(num)
        if k <= len(nums1):
            return self.findKthLargest(nums1, k)
        if k > len(nums) - len(nums2):
            return self.findKthLargest(nums2, k - (len(nums) - len(nums2)))
        return pivot

O(nlogn)解法：排序

class Solution:
    # @param {integer[]} nums
    # @param {integer} k
    # @return {integer}
    def findKthLargest(self, nums, k):
        return sorted(nums, reverse=True)[k - 1]

 

本文链接：http://bookshadow.com/weblog/2015/05/23/leetcode-kth-largest-element-array/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码