algorithm - QuickSelect 能否找到具有重复值的数组中的最小元素？

Question

QuickSelect 算法是否适用于重复值？

如果我有一个数组

int[] array = {9, 8, 7, 6, 6, 6, 5, 0, 1, 2, 3, 4, 5, 5, 7, 200};

即使有重复也能得到第k小的元素吗？

Answer 1

是的，它有效。在每次迭代结束时，所有小于当前主元的元素都存储在主元左侧。

让我们考虑所有元素都相同的情况。在这种情况下，每次迭代最终都会将枢轴元素放在数组的左侧。下一次迭代将继续使用一个元素更短的数组。所以我们需要 k 次迭代来找到第 k 个最小的元素。