第K序元素查找
在无排序的一一个列表中查找第k个最大元素。
例如,给定3,2,1,5,6,4和k=2,返回5。
注意:假设k总是有效的,0<= k < =数组的长度
第一种
import heapq
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
L = []
for index in range(k):
# 默认是最小堆
heapq.heappush(L, nums[index])
for index in range(k, len(nums)):
top = L[0]
if nums[index] > top:
# 看一看堆顶的元素,只要比堆顶元素大,就替换堆顶元素
heapq.heapreplace(L, nums[index])
# 最后堆顶中的元素就是堆中最小的,整个数组中的第 k 大元素
return L[0]
if __name__ == '__main__':
nums = [3, 7, 8, 1, 2, 4]
solution = Solution()
result = solution.findKthLargest(nums, 2)
print(result)
第二种:
class Solution:
# 数组中的第 K 个最大元素
# 数组中第 k 大的元素,它的索引是 len(nums) - k
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
left = 0
right = len(nums) - 1
while True:
index = self.__partition(nums, left, right)
if index == len(nums) - k:
return nums[index]
if index > len(nums) - k:
right = index - 1
else:
left = index + 1
def __partition(self, nums, left, right):
"""
partition 是必须要会的子步骤,一定要非常熟练
典型的例子就是:[3,7,8,1,2,4]
遇到比第一个元素大的或等于的,就放过,遇到小的,就交换
在 [left,right] 这个区间执行 partition
:param nums:
:param left:
:param right:
:return:
"""
pivot = nums[left]
k = left
for index in range(left + 1, right + 1):
if nums[index] < pivot:
k += 1
nums[k], nums[index] = nums[index], nums[k]
nums[left], nums[k] = nums[k], nums[left]
return k
if __name__ == '__main__':
nums = [3, 7, 8, 1, 2, 4]
solution = Solution()
result = solution.findKthLargest(nums, 2)
print(result)
list1 = [int(i) for i in input().strip().split(',')]
k = int(input().strip())
new_list = sorted(list1, reverse=True)
print(new_list[k-1])