TopK大问题的另一种解法
不久前介绍了堆排序Python堆排序之heapq，主要是解决下面这个题目
在未排序的数组中找到第 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 ≤ 数组的长度。
这是很经典的题目，有很多解法，除了上面说到的最小堆：heapq之外，今天复习的时候，又发现大佬的另一种解法，可以说是想法独特了。专门来记录下。
下面是源码：
class Solution:
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
a = nums[:k]
temp_min = min(a)
for i in nums[k:]:
if i > temp_min:
a.remove(temp_min)
a.append(i)
temp_min = min(a)
return temp_min这种方法就是把原列表分为两部分，以K作为索引分割为A、B两个列表，然后遍历B列表，把里面每个元素拿来和A列表中的最小值比较，最终目的是保证A列表是原列表中数据最大的部分。
这个想法在别的解题方法中还真没见过，很多人用的是“偷懒”的方法，面试中肯定用不了。还有些用的是排序来做的，代码量就比较大了。
前方高能
class Solution:
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
# nums.sort()
# return nums[-k]
import random
def partition(nums, left, right):
p = random.randint(left, right)
nums[p], nums[right] = nums[right], nums[p]
i = left - 1
for j in range(left, right):
if nums[j] <= nums[right]:
i += 1
nums[i], nums[j] = nums[j], nums[i]
nums[i+1], nums[right] = nums[right], nums[i+1]
# print(nums[p])
return i+1
def select(nums, left, right, k):
if left == right:
return nums[left]
p = partition(nums, left, right)
pos = p - left + 1
if k == pos:
return nums[p]
elif k < pos:
return select(nums, left, p-1, k)
else:
return select(nums, p+1, right, k-pos)
return select(nums, 0, len(nums)-1, len(nums)-k+1)本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-12-25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读