思路:我们利用快排分区的思想来解答这个问题,我们以数组最后一个元素记为 pivot, 将数组分为三个部分,a[0..q-1], a[q],a[q+1...r],然后我们比较 q+1 是否等于 k , 如果相等,我们返回 a[q],q+1 > k,我们在 a[0,q-1] 中递归寻找。时间复杂度分析:第一次分区,我们查找了 n 个元素,第二次我们查找了 n/2 个元素,依次类推,最后区间缩小到 1,复杂度为 n+n/2 + n/4 + ....+1 为 O(2n-1) 即 O(n)。 import java.util.*; public class Finder { publi...