【LeetCode215】数组中的第K个最大元素

题目地址

1. 基本思路

用一个基准数e将集合S分解为不包含e在内的两个小集合 $S_{1}$ 和 $S_{2}$ ，其中 $S_{1}$ 的任何元素均大于等于e， $S_{2}$ 的任何元素均小于e，记 $∣ S ∣$ 代表集合S元素的个数，这样，如果 $|S_{1}|\ge K$ ，则说明第K大数在 $S_{1}$ 中；如果 $S_{1}|$ 恰好等于K-1，说明e是第K大数；否则第K大数在 $S_{2}$ 中，并且是 $S_{2}$ 中的第 $K-|S_{1}|-1$ 大数。然后，可以用类似的思路继续在 $S_{1}$ 或 $S_{2}$ 中查找。
其实这就是快速排序划分数组的过程

2. 最后一个巨型测试用例不通过的代码

//求划分
//其实这个方法就是快速排序求划分的过程
int divide(int* nums, int left, int right)
{//基准数e选nums[left]，题目中的数组非空，不用判断特殊情况int e = nums[left];//接下来要把数组分成两部分，一部分小于e，一部分大于等于ewhile (left < right){//让right一直向左移动，直到找到比基准数e小的数，并让这个元素传入left的位置while (left < right && nums[right] >= e){right--;}nums[left] = nums[right];//让left一直向右移动，直到找到比基准数e大的数，并让这个元素传入right的位置while (left < right && nums[left] <= e){left++;}nums[right] = nums[left];}nums[left] = e; //基准数最终存放的位置return left; //返回基准数的新下标
}
//递归用的helper
int findKthLargestHelper(int* nums, int left, int right, int k)
{// 数组S1的元素都大于等于基准数e，但是S1不包括基准数e，先求出基准数的下标e_index// 数组S2就是0到S1_start - 1这些下标对应的元素int e_index = divide(nums, left, right);// 求出S1的长度(注意，S1不包括基准数e），right - e_index - 1 + 1即right - e_indexint len_S1 = right - e_index;// 如果S1长度大于kif (len_S1 >= k){//S1和S2都不包括基准数ereturn findKthLargestHelper(nums, e_index + 1, right, k);}else if (len_S1 < k - 1){return findKthLargestHelper(nums, left, e_index - 1, k - len_S1 - 1);}else //恰好S1长度为k-1，说明基准数是第k大的数{return nums[e_index];}
}
int findKthLargest(int* nums, int numsSize, int k) {//如果使用递归，最后一个巨大的测试用例无法通过，故使用循环int left = 0;int right = numsSize - 1;// 数组S1的元素都大于等于基准数e，但是S1不包括基准数e，先求出基准数的下标e_index// 数组S2就是0到S1_start - 1这些下标对应的元素int e_index = 0; //先初始化为0// 求出S1的长度(注意，S1不包括基准数e），right - e_index - 1 + 1即right - e_indexint len_S1 = 0; //先初始化为0while(left <= right){e_index = divide(nums, left, right);len_S1 = right - e_index;// 如果S1长度大于kif (len_S1 >= k){//就继续去S1数组中继续分割left = e_index + 1;//k值不变}else if (len_S1 < k - 1){//去S2数组中继续分割right = e_index - 1;//k值变化k = k - len_S1 - 1;}else{//恰好S1长度为k-1，说明基准数是第k大的数return nums[e_index];}}return nums[e_index];
}

正好卡在最后一个测试用例：

没通过的原因是，我们取的基准值不是从数组中选的随机值，接下来修改代码

3. 选用随机值的快速排序划分

//生成从x到y的整数随机数
int getIntRandom(int x, int y)
{// 传入时间戳，生成伪随机数srand((unsigned int)time(NULL));return (int)(x + (rand() % (y - x + 1)));
}
//求划分
//其实这个方法就是快速排序求划分的过程
int divide(int* nums, int left, int right)
{//随机选一个基准数的下标int random_index = getIntRandom(left, right);// 基准值int e = nums[random_index];// 将nums[random_index]和nums[left]互换，方便后来交换int temp = nums[random_index];nums[random_index] = nums[left];nums[left] = temp;//接下来要把数组分成两部分，一部分小于e，一部分大于等于ewhile (left < right){//让right一直向左移动，直到找到比基准数e小的数，并让这个元素传入left的位置while (left < right && nums[right] >= e){right--;}nums[left] = nums[right];//让left一直向右移动，直到找到比基准数e大的数，并让这个元素传入right的位置while (left < right && nums[left] <= e){left++;}nums[right] = nums[left];}nums[left] = e; //基准数最终存放的位置return left; //返回基准数的新下标
}
//递归用的helper
int findKthLargestHelper(int* nums, int left, int right, int k)
{// 数组S1的元素都大于等于基准数e，但是S1不包括基准数e，先求出基准数的下标e_index// 数组S2就是0到S1_start - 1这些下标对应的元素int e_index = divide(nums, left, right);// 求出S1的长度(注意，S1不包括基准数e），right - e_index - 1 + 1即right - e_indexint len_S1 = right - e_index;// 如果S1长度大于kif (len_S1 >= k){//S1和S2都不包括基准数ereturn findKthLargestHelper(nums, e_index + 1, right, k);}else if (len_S1 < k - 1){return findKthLargestHelper(nums, left, e_index - 1, k - len_S1 - 1);}else //恰好S1长度为k-1，说明基准数是第k大的数{return nums[e_index];}
}
int findKthLargest(int* nums, int numsSize, int k) {//如果使用递归，最后一个巨大的测试用例无法通过，故使用循环int left = 0;int right = numsSize - 1;// 数组S1的元素都大于等于基准数e，但是S1不包括基准数e，先求出基准数的下标e_index// 数组S2就是0到S1_start - 1这些下标对应的元素int e_index = 0; //先初始化为0// 求出S1的长度(注意，S1不包括基准数e），right - e_index - 1 + 1即right - e_indexint len_S1 = 0; //先初始化为0while(left <= right){e_index = divide(nums, left, right);len_S1 = right - e_index;// 如果S1长度大于kif (len_S1 >= k){//就继续去S1数组中继续分割left = e_index + 1;//k值不变}else if (len_S1 < k - 1){//去S2数组中继续分割right = e_index - 1;//k值变化k = k - len_S1 - 1;}else{//恰好S1长度为k-1，说明基准数是第k大的数return nums[e_index];}}return nums[e_index];
}