[leetcode]215. Kth Largest Element in an Array

本文主要是介绍[leetcode]215. Kth Largest Element in an Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给一个数组，求出数组中的第K大数，比如[3,2,1,5,6,4] 求出第2大数，则为5

分析：

复习堆排序，对于这道题来讲，找第k大数，可以通过一个小顶堆实现。首先取数组中的前k个数组成小顶堆（具体堆的调整可以百度，或者看代码应该就理解），此时堆顶的数字就是这k个数字里面的第K大数，然后从每次从剩余的数组中拿出一个数字和堆顶的数字进行比较，如果比堆顶数字小，则直接丢弃；如果大于堆顶数字，则替换该数字，重新进行堆调整，调整完成之后堆顶的数字依旧是已经处理过的数字中的第K大数。如此重复执行，直到数据处理完毕，此时堆顶的数字就是第K大数

代码：

#!/usr/bin/env python
class Solution(object):def __init__(self):self.nums_t = []def min_heap(self, i, l):L = i * 2R = i * 2 + 1min = iif L <= l and self.nums_t[L-1] < self.nums_t[i-1]:min = Lif R <= l and self.nums_t[R-1] < self.nums_t[min-1]:min = Rif min != i:tp = self.nums_t[min-1]self.nums_t[min-1] = self.nums_t[i-1]self.nums_t[i-1] = tpself.min_heap(min, l)def build_min_heap(self):l = len(self.nums_t)for i in range(l/2, 0, -1):self.min_heap(i, l)def findKthLargest(self, nums, k):self.nums_t = nums[0:k]self.build_min_heap()nums_leave = nums[k:]LL = len(nums_leave)for i in range(0, LL):if nums_leave[i] > self.nums_t[0]:self.nums_t[0] = nums_leave[i]self.min_heap(1, len(self.nums_t))return self.nums_t[0]
# 下面为测试代码
if __name__ == '__main__':nums = [4,1,3,2,16,9,10,14,8,7]l = 5s = Solution()ans = s.findKthLargest(nums, l)print "ans : ", ans

如代码所示，对于前K个数字进行建小顶堆，然后对于剩余的数字进行比较处理，最后堆顶数字即为所求

这篇关于[leetcode]215. Kth Largest Element in an Array的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---