随机选择算法

题目背景：

无序数组中寻找第K大的数

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

题目的要求是返回数组中第k个最大元素，如果第k个元素左右有元素值与其相等，仍返回该元素。

基于这样的特点，不难想到可以使用之前学过的随机快速排序，在其优化算法中，整个区间被分成了三段，我们要使用的只有其中的两段，一段是中间的i = x 区域，这说明这次随机命中了题目要求的第k个元素，随即返回。但若没有命中，比较中间区域的两端，看k属于哪侧，便继续在哪侧中递归执行此过程。

题目要求将时间复杂度控制在O(n)内，由于我们并未像快排那样对两侧区间进行递归，而是对一侧或不对半区间进行递归，即时间复杂度变更为O(n+n/2+n/4+n/8...)~O(n)。