第k个最大/最小元素是什么意思？

Question

我目前正在研究选择算法，即中位数。

我遇到了下面两个句子:

在计算机科学中，选择算法是寻找列表或数组中第k个最小数的算法；

在计算机科学中，中位数是一种近似(中位数)选择算法，经常用于为精确选择算法(主要是quickselect)提供良好的中枢，该算法选择最初未排序数组的第k个最大元素。

第k个最小/最大元素是什么意思？为了使问题更具体一点，考虑以下(未排序)数组:

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

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

Answer 1

如果按从小到大的顺序对数组进行排序，则第 k 个最小元素是排序数组中的第 k 个元素。第 k 个最大元素是排序数组中从末尾开始的第 k 个元素。让我们检查一下 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 个最小的是左边的第 k 个元素。同样，24是最大的，23是第二大的，依此类推，所以第k大元素是右边的第k个元素。因此，如果 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个最小/最大值而对数组进行排序。排序只是一种简单的方法，可以看出哪个值对应于k。