代码拉取完成,页面将自动刷新
"""
Find the kth smallest element in linear time using divide and conquer.
Recall we can do this trivially in O(nlogn) time. Sort the list and
access kth element in constant time.
This is a divide and conquer algorithm that can find a solution in O(n) time.
For more information of this algorithm:
https://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/08/Small08.pdf
"""
from __future__ import annotations
from random import choice
def random_pivot(lst):
"""
Choose a random pivot for the list.
We can use a more sophisticated algorithm here, such as the median-of-medians
algorithm.
"""
return choice(lst)
def kth_number(lst: list[int], k: int) -> int:
"""
Return the kth smallest number in lst.
>>> kth_number([2, 1, 3, 4, 5], 3)
3
>>> kth_number([2, 1, 3, 4, 5], 1)
1
>>> kth_number([2, 1, 3, 4, 5], 5)
5
>>> kth_number([3, 2, 5, 6, 7, 8], 2)
3
>>> kth_number([25, 21, 98, 100, 76, 22, 43, 60, 89, 87], 4)
43
"""
# pick a pivot and separate into list based on pivot.
pivot = random_pivot(lst)
# partition based on pivot
# linear time
small = [e for e in lst if e < pivot]
big = [e for e in lst if e > pivot]
# if we get lucky, pivot might be the element we want.
# we can easily see this:
# small (elements smaller than k)
# + pivot (kth element)
# + big (elements larger than k)
if len(small) == k - 1:
return pivot
# pivot is in elements bigger than k
elif len(small) < k - 1:
return kth_number(big, k - len(small) - 1)
# pivot is in elements smaller than k
else:
return kth_number(small, k)
if __name__ == "__main__":
import doctest
doctest.testmod()
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。