leetCode-215:Kth Largest Element in an Array

问题描述

给定一个整数数组和数字 k，要求找出数组中第 k 大的数字。题目链接：**点我**

样例输入输出

输入：nums = [3,2,1,5,6,4], k = 2

输出：5

输入：nums = [3,2,3,1,2,4,5,5,6], k = 4

输出：4

问题解法

使用快排的思想进行求解，先挑选一个数，对数组进行划分，大于等于这个数的放数组右边，小于这个数的放数组左边，然后看右边的数量是否大于 k，如果大于 k，则在右边的子数组中继续上述过程的查找，如果小于 k，则在左边的子数组中继续上述过程查找，如果等于 k，则说明当前这个值就是要求解的值。代码如下

class Solution
{
    public int findKthLargest(int[] nums, int k)
    {
        return findKthNum(nums, 0, nums.length - 1, k);
    }

    private int findKthNum(int[] nums, int from, int to, int k)
    {
        int index = to;
        int start = from;
        int end = to;
        while (start < end)
        {
            if (nums[start] < nums[index])
            {
                start++;
                continue;
            }

            if (nums[end] >= nums[index])
            {
                end--;
                continue;
            }

            swap(nums, start, end);
        }

        if (nums[start] > nums[index])
        {
            swap(nums, start, index);
        }

        if (to - start + 1 == k)
        {
            return nums[start];
        }

        if (to - start + 1 > k)
        {
            return findKthNum(nums, start + 1, to, k);
        }

        return findKthNum(nums, from, start - 1, k - to + start - 1);
    }

    private void swap(int[] nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}