<p>我已经编写了一些python代码,用于获取未排序数组中的第k个最小元素。我想获得帮助来反转函数以获得第k个最大元素。我知道StackOverflow上还有其他问题可以回答这个问题,但老实说,我来这里不是因为我想我的问题得到回答。我来这里是因为我想要这个模式,如何思考这样的问题,这样下次我看到这样的问题时,我就能回答。因此,请向我解释清楚,帮助我真正理解该做什么,以便我将来可以解决类似的问题</p>
<pre><code>from typing import List
def partition(array: List[int], lowerbound: int, upperbound: int) -> int:
"""
Partitions the array so that lower items are to the left of the pivot and bigger items are to the right.
"""
pivot = array[upperbound]
index_1 = lowerbound - 1
for index_2 in range(lowerbound, upperbound): # we loop from lowerbound and stop just before the pivot.
if array[index_2] < pivot: # if the value at index 2 is less than the pivot.
index_1 += 1
array[index_1], array[index_2] = array[index_2], array[index_1] # swap index one and two
array[index_1 + 1], array[upperbound] = array[upperbound], array[index_1 + 1]
return index_1 + 1 # return the pivot(basically it's index)
def quick_select(array: List[int], lowerbound: int, upperbound: int, item_index: int) -> int:
"""
Performs the quick select algorithm.
"""
if lowerbound >= upperbound:
return array[lowerbound]
pivot_index = partition(array, lowerbound, upperbound)
if pivot_index == item_index:
return array[item_index]
if pivot_index > item_index:
return quick_select(array, lowerbound, pivot_index - 1, item_index)
else:
return quick_select(array, pivot_index + 1, upperbound, item_index)
```
</code></pre>