写作目的:总结一下本题疑惑的点
代码基本和y老师的差不多,思路也一样,不多赘述,我在看y老师讲解时,最大的困惑是为什么l == r时,就是正确的答案。
y老师说,因为我们保证了每一轮都会把答案放在区间里,所以如果区间只剩一个点,那肯定是答案,这种回答简洁明了,但是我一开始没绕出来的是怎么保证最后一定能只剩一个。
其实想明白了很简单(我 是 傻 逼),因为随着快排的进行,左边的数迟早会小于k,下一轮的递归就会去右边,这样继续递归的k值就会不断减少,从而以后递归的区间长度就会不断变小,最后一定会只剩一个。
这题绕住我的地方就这么多,以上。