通过快速选择获得第k个最大元素

Question

我已经编写了一些python代码，用于获取未排序数组中的第k个最小元素。我想获得帮助来反转函数以获得第k个最大元素。我知道StackOverflow上还有其他问题可以回答这个问题，但老实说，我来这里不是因为我想我的问题得到回答。我来这里是因为我想要这个模式，如何思考这样的问题，这样下次我看到这样的问题时，我就能回答。因此，请向我解释清楚，帮助我真正理解该做什么，以便我将来可以解决类似的问题

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)
    ```

Answer 1

对于相同的代码，获得第k个最大值是至关重要的，您只需以另一种方式索引即可

完全未经测试的代码

def KthLargest(array: List[int], item_index: int)
  return quick_select(array, 0, len(List), len(list)-item_index) # off-by-one?

Answer 2

至少有两种方法：

• 第K个最大值是第（N+1-K）个最小值，您甚至不需要重写算法

• 在给定的代码中，只要有元素比较，就翻转其方向（将>；转到<；，>；=转到<；=等等）。注意：我的意思是元素比较仅

---

另一种选择是更改数组中所有元素的符号，查找最小的元素并恢复符号

我不推荐这种方法，除非符号的改变是虚拟的，即在涉及元素的陈述中假设。例如a>；b被重写-a>-b、 这也是一个<；b、 这让我们回到第二种方法