python--查数组第K⼤的数
这个问题应该是⽐较经典的，要求能在时间复杂度O（n）解决。
最暴⼒的⽅法当然是先排个序，时间复杂度是O(nlogn)，但是这样浪费了很多不必要的计算。
O（n）的算法思想借鉴了快排的思想：
快速排序每次把⼀个元素交换到正确的位置，同时把左边的都放上⼤的，右边都放上⼩的。这个算法每⼀次选取⼀个枢纽元，排序之后，查看枢纽元的位置。如果它的位置⼤于K，就说明，要求出前⾯⼀个⼦序列的第K⼤的元素。反之，如果⼩于K，就说明要求出在后⾯⼀个序列的第K - 前⼀个序列的长度个元素。
如此，就把这个问题改变成了⼀个可以⽤快排思想解决的问题。对于快速排序，算法复杂度是O(N*logN)。⽽这个算法的算法复杂度是
O(N)。为什么呢？
其实这个地⽅的算法复杂度分析很有意思。第⼀次交换，算法复杂度为O(N)，接下来的过程和快速排序不同，快速排序是要继续处理两边的数据，再合并，合并操作的算法复杂度是O(1)，于是总的算法复杂
度是O(N*logN)（可以这么理解，每次交换⽤了N，⼀共logN次）。但是这⾥在确定枢纽元的相对位置（在K的左边或者右边）之后不⽤再对剩下的⼀半进⾏处理。也就是说第⼆次插⼊的算法复杂度不再是O(N)⽽是O(N/2)，这不还是⼀样吗？其实不⼀样，因为接下来的过程是1+1/2+1/4+........ < 2，换句话说就是⼀共是O(2N)的算法复杂度也就是O(N)的算法复杂度。
看到评论后，我修改了代码，⽬前的代码已经没有bug了。代码实现：
def kthLargestElement(k, A):
if not A or k < 1 or k > len(A):
return None
return partition(A, 0, len(A) - 1, len(A) - k)
def partition(nums, start, end, k):
"""
快速排序python实现
During the process, it's guaranteed start <= k <= end
"""
if start == end:
return nums[k]
left, right = start, end
pivot = nums[(start + end) // 2]
while left <= right:
while left <= right and nums[left] < pivot:
left += 1
while left <= right and nums[right] > pivot:
right -= 1
if left <= right:
nums[left], nums[right] = nums[right], nums[left]
left, right = left + 1, right - 1
# left is not bigger than right
if k <= right:
return partition(nums, start, right, k)
if k >= left:
return partition(nums, left, end, k)
return nums[k]
pai = [2, 3, 1, 5, 4, 6,7,2,3]
print(kthLargestElement(9,pai))

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。