【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，一部分大于等于e
    while (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_index
    int len_S1 = right - e_index;
    // 如果S1长度大于k
    if (len_S1 >= k)
    {
        //S1和S2都不包括基准数e
        return 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_index
    int len_S1 = 0; //先初始化为0
    while(left <= right)
    {
        e_index = divide(nums, left, right);
        len_S1 = right - e_index;
        // 如果S1长度大于k
        if (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，一部分大于等于e
    while (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_index
    int len_S1 = right - e_index;
    // 如果S1长度大于k
    if (len_S1 >= k)
    {
        //S1和S2都不包括基准数e
        return 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_index
    int len_S1 = 0; //先初始化为0
    while(left <= right)
    {
        e_index = divide(nums, left, right);
        len_S1 = right - e_index;
        // 如果S1长度大于k
        if (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];
}

提交结果：