随机选择算法

在一个无序数组中求第k大或者第k小的问题，要求时间复杂度是O(N),那么对于这两个问题只要解决一个另一个就解决了。因为求第一大可以转换成求第n小。

那么对于一个有100个元素的数组来说，我们要求第57小的数，那么它就是在求这个数组排好序之后下标在56的值，因为如果数组的元素没有重复的话，那么在下标0位置的数一定是第一小的数，第二小的数一定是在下标1位置的数。那么对于一个有重复元素的数组，也是一样的。我们并不是要求去掉重复元素之后第k小的元素，注意题目的意思。因此对于找第k小实际上就是返回数组从小到大排完序之后第k - 1个位置，例如[1, 1, 2, 3]求第二小的数，实际上就是求数组从小到大排序之后，下标1位置的数是什么，第2小的数是1，而不是2，因为不是求去重之后第k小的数，所以第一小的数是1，第二小的数还是1，第三小的数是2，第四小的数是3。那么分析完毕，就可以写code了。

解题思路

1. 利用快速排序分区的思想来进行查找。
2. 如果要找的下标在等于区间之中，那么直接返回等于区间的值就可以了。
3. 如果要找的下标在等于区间的右边，那么只要在等于区间的右边找
4. 如果要找的下标在等于区间的左边，那么只要在等于区间的左边找
5. 重复以上步骤

代码实现

void partition(int *a, int l, int r, int key);//按照key来分区
void swap(int *a, int i, int j) {
	int t = a[i];
	a[i] = a[j];
	a[j] = t;
}
int left;//记录等于区间的左边界
int right;//记录等于区间的右边界

int findKthLargest(int* nums, int numsSize, int k) {    
    int l = 0;//初始化左边界
    int r = numsSize - 1;//初始化右边界
    int ans = 0;

    srand(time(0));

    k = numsSize - k;//找第k大的元素，等于找下标numsSize - k的值

    while(l <= r) {//如果区间中还有元素
        partition(nums, l, r, nums[l + rand() % (r - l + 1)]);//随机出来一个数来分区
        if (k < left) {//如果要找的下标在左边
            r = left - 1;//更新右边界，因为只能在左边了
        }
        else if (k > right) {//更新左边界，因为只能在右边了
            l = right + 1;//更新左边界，因为只能在右边了
        }
        else {//找到了
            ans = nums[left];//给ans赋值，并且跳出循环
            break;
        }
    }

    return ans;
}
void partition(int *a, int l, int r, int key)
{
    int lb = l;//等于区间的左边界
    int rb = r;//等于区间的右边界
    int i = l;//遍历的下标

    while(i <= rb) {//只要没有到大于区间 
		if (a[i] < key) {//下标i的数小于基准值，放在左边界里面 
			swap(a, lb++, i++);//把左边界的后一个数和下标i的值交换，然后左区间扩张，然后去看下一个数 
		}
		else if ( a[i] > key){//下标i的数大于基准值，放在右边界里面 
			swap(a, rb--, i);//把右边界的前一个数和下标i的值做交换，然后右区间扩张，但i不能动，因为当前i的值还没有访问过 
		}
		else {//下标i的数等于基准值，放在左右边界之间 
			i++;//直接加1
		}
	} 

    left = lb;//更新left的值
    right = rb;//更新right的值
}

这个代码的时间复杂度是O(N),这个也是用数学期望求解的时间复杂度，因为它用了随机。就只能用数学期望来估计时间复杂度。空间复杂度O(1)。