数组中第K个最大元素（算法村第十关白银挑战）

215. 数组中的第K个最大元素 - 力扣（LeetCode）

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

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

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

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

解

6-4 随机选择切分元素_哔哩哔哩_bilibili

public int findKthLargest(int[] nums, int k)
    {
   
    	// 第 1 大的数，下标是 len - 1;
        // 第 2 大的数，下标是 len - 2;
        // ...
        // 第 k 大的数，下标是 len - k;
        int targetPos = nums.length - k;
        int low = 0;
        int high = nums.length - 1;

        while (true)
        {
   
            int pivotPos = partition(nums, low, high);

            if(pivotPos == targetPos)
                return nums[pivotPos];
            else if(pivotPos < targetPos)
                low = pivotPos + 1;
            else
                high = pivotPos - 1;
        }
    }

public static int partition(int[] nums, int low, int high)
{
   
    //取（子）序列第一个元素为基准元素
    int pivot = nums[low];  //此时 low 为坑位

    while (low < high)
    {
   
        //先从右边找，填补左边的坑位
        while (low < high && nums[high] >= pivot)
            high--;
        nums[low] = nums[high]; //而后 high 成了坑位

        //再从左边找，填补右边的坑位
        while (low < high && nums[low] <= pivot)
            low++;
        nums[high] = nums[low];
    }

    nums[low] = pivot; //或 nums[high] = pivot
    return low; //或 return high
}

执行用时：2608 ms

优化 partition

public static Random random = new Random(System.currentTimeMillis());

public static int partition_2(int[] nums, int low, int high)
{
   
    //在 [low, high] 中随机取一个位置 randomPos, 将 nums[randomPos] 设为pivot
    int randomPos = low + random.nextInt(high - low + 1);

    //仍然将 low 设为坑位
    swap(nums,low,randomPos);	//交换 low 和 randomPos 位置上的数
    int pivot = nums[low];

    while (low < high)
    {
   
        //先从右边找，填补左边的坑位
        while (low < high && nums[high] >= pivot)
            high--;
        nums[low] = nums[high]; //而后 high 成了坑位

        //再从左边找，填补右边的坑位
        while (low < high && nums[low] <= pivot)
            low++;
        nums[high] = nums[low];
    }

    nums[low] = pivot; //或 nums[high] = pivot
    return low; //或 return high
}

public static void swap(int[] nums, int i, int j)
{
   
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}

执行用时：853 ms

算法还能再优化

…