有一篇题解有大问题！！！

szm111213 @ 2024-12-20 14:35:11

by chenxi2009 @ 2024-12-20 14:44:18

@时律

by Mr_Terminator @ 2024-12-20 14:46:58

@szm111213 怎么了，每次期望砍成原数列的一半大小去找，怎么你了。时间复杂度 O(\sum_{i}\frac{n}{2_i})=O(n)。又不是要把整个数列排一遍，慌啥

by Mr_Terminator @ 2024-12-20 14:47:32

@szm111213 他说的是快排思想，怎么是没见过这个词吗

by Mr_Terminator @ 2024-12-20 14:48:09

妈的，脑子熔化了，^ 打成 _ 了

by szm111213 @ 2024-12-20 14:50:04

@Mr_Terminator 二分的前提条件是有序，你都要排序你怎么用二分

by Mr_Terminator @ 2024-12-20 15:18:57

@szm111213

1. 随机选择一个幸运的元素

2. 线性地把所有小于等于它的元素推到左边，大于它的元素推到右边

3. 如果 rank<=左边的元素数量大小，去左边，否则去右边

by Mr_Terminator @ 2024-12-20 15:19:14

只要够随机就死不了

by szm111213 @ 2024-12-20 15:19:52

@Mr_Terminator emm，算你赢

by EarthMessenger @ 2024-12-20 16:03:01

@Mr_Terminator 你是分不清二分和分治嗎？

by Mr_Terminator @ 2024-12-20 16:07:35

@EarthMessenger 这就是类似于把原问题缩小为一半啊

分治是 4->2+2，二分是 4->2，分不清的不是我