美文网首页
215. 数组中的第K个最大元素(medium)

215. 数组中的第K个最大元素(medium)

作者: genggejianyi | 来源:发表于2019-06-19 17:10 被阅读0次

在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。

  • show the code:
class Solution(object):  
    def partition(self,a,lo,hi):
        pivot = a[lo]# 选取第一个为枢轴值
        while lo < hi:
            while lo < hi and a[hi] <= pivot:
                hi -= 1
            a[lo] = a[hi]
            while lo < hi and a[lo] >= pivot:
                lo += 1
            a[hi] = a[lo]
        a[lo] = pivot
        return lo
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        return self.quicksort(nums,0,len(nums)-1,k)
    def quicksort(self,nums,begin,end,k):
        if begin >= end:
            return nums[begin]
        mid = self.partition(nums,begin,end)
        if mid == k-1:
            return nums[mid]
        elif mid > k-1:
            return self.quicksort(nums,0,mid-1,k)
        else:
            return self.quicksort(nums,mid+1,end,k)
  • 此题的重点是写出partition函数,由于是选出topk大的数,我们partition函数作用就是将比临界值大的数分在其左边,比临界值小的数分在右边。因此我们利用双指针,从左边右边分别开始循环,这里需要注意:如果我们选择第一个数作为临界值,那么就要从右边开始寻找“异常值”(比临界值大的值)如果我们选择最后一个数作为临界值,那么就要从左边开始寻找“异常值”
  • 然后利用两步赋值完成交换,最后在双指针碰撞时,将临界值插入数组中,返回临界值的索引。
  • 写出partition函数后就好做了,每一次partition后都能把一个数放到其正确排序位置上,可以不断缩小寻找范围。
  • 时间复杂度介于O(N)和O(N^2)之间,一般可以达到O(N)

相关文章

网友评论

      本文标题:215. 数组中的第K个最大元素(medium)

      本文链接:https://www.haomeiwen.com/subject/rhgkqctx.html