不久前介绍了堆排序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)
本文分享自 Python爬虫与算法进阶 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!