kth最大/最小元素是什么意思？

Question

我目前正在研究选择算法，也就是中间值。

我遇到了两句话：

在计算机科学中，选择算法是一种在列表或数组中求最小数的算法； 在计算机科学中，中间值是一种近似(中值)选择算法，经常用于为精确选择算法(主要是快速选择算法)提供一个好的支点，该算法选择初始未排序数组的kth最大元素。

kth最小/最大元素是什么意思？为了使问题更加具体，请考虑以下(未排序的)数组：

[19, 1, 7, 20, 8, 10, 19, 24, 23, 6]

例如，第五个最小元素是什么？第五大元素是什么？

Answer 1

如果将数组从最小排序到最大排序，则_k_th最小元素是排序数组中的_k_th元素。_k_th最大的元素是排序数组末尾的_k_th。让我们检查一下Python中的示例数组：

In [2]: sorted([19, 1, 7, 20, 8, 10, 19, 24, 23, 6])
Out[2]: [1, 6, 7, 8, 10, 19, 19, 20, 23, 24]

最小的元素是1，第二最小的是6，依此类推。所以k_th最小的是左边的_k_th元素。同样，24是最大的，23是第二大的，依此类推，所以_k_th最大的元素是右边的_k_th元素。所以如果_k =5

In [3]: sorted([19, 1, 7, 20, 8, 10, 19, 24, 23, 6])[4]  # index 4 is 5th from the start
Out[3]: 10

In [4]: sorted([19, 1, 7, 20, 8, 10, 19, 24, 23, 6])[-5] # index -5 is 5th from the end
Out[4]: 19

请注意，不必对数组进行排序才能得到最小/最大的k_th值。排序只是查看哪个值对应于_k的一种简单方法。