第k小如果有重复数据呢

如果有一样的元素 k-1 可能取的值对不上阿

源自：快速排序法 2-9 作业：Select K 问题

收起

1回答

liuyubobobo 回答被采纳获得+3积分 2021-03-23 06:36:31

我没有特别理解你的意思，什么叫“对不上”？

在这里，我介绍的算法，等价于求解：把原数组进行排序后，第 k - 1 索引位置的元素的是谁。

如果进行排序再取值，时间是 O(nlogn) 的，使用这个 selectK 算法，是 O(n) 的。

继续加油！：）

旋涡鸣人_ 提问者 #1

1, 1, 2, 2, 3, 3
0 1 2 3 4 5
第k小的元素
k = 1 1 - 1 = 0 value: 1
k = 2 2 - 1 = 1 value: 1 表示K等于2 的时候，结果还是1。第二小的元素不应该是 2 吗？

2021-03-24 12:07:01
liuyubobobo 回复提问者旋涡鸣人_ #2

你对第 k 小的定义和这个算法对第 k 小的定义不同。这个算法求解：把原数组进行排序后，第 k - 1 索引位置的元素的是谁。按照你的定义，需要先对数组去重。

2021-03-24 13:42:03