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 个最小的元素。