[LeetCode]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.

题目大意:

从一个未经排序的数组中找出第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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

评论
  1. Judge Judge 发布于 2018年1月12日 11:06 #

    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(N)么 但题目要求的是O(1)

张贴您的评论