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

Question

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

如果我有阵列

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

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

Answer 1

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

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