题目描述

  给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

解析

  快速排序的思想：每次确定当前轴的位置，因此可以对快速排序算法进行修改，每次找轴的位置，如果小则对后半进行递归，大则对前半部分进行递归。

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

    public int quickSort(int[] nums, int left, int right, int k){
        if (left == right) {
            return nums[left];
        }
        int base = nums[left];
        int low = left + 1;
        int high = right;
        while(low <= high) {
            while(low <= high && nums[low] <= base) {
                low ++;
            }
            while(low <= high && nums[high] > base) {
                high --;
            }
            if(low < high) {
                swap(nums, low, high);
            }
        }

        if(high == k) {
            return nums[left];
        }

        swap(nums, left, high);

        if(high < k) {
            return quickSort(nums, high + 1, right, k);
        }
        else {
            return quickSort(nums, left, high - 1, k);
        }
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

  实际上，如果数据量不是特别大，可以更改算法，更简单且快捷。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int max = Arrays.stream(nums).max().getAsInt();
        int min = Arrays.stream(nums).min().getAsInt();
        int range = max - min + 1;
        int[] buckets = new int[range];
        
        for (int num : nums) {
            buckets[num - min]++;
        }

        for (int i = range - 1; i >= 0; i--) {
            k -= buckets[i];
            if (k <= 0) {
                return i + min;
            }
        }
        return -1;
    }
}

  针对上述解法，可以针对题目的输入进行时间优化.

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int[] buckets = new int[20001];
        for (int i = 0; i < nums.length; i++) {
            buckets[nums[i] + 10000]++;
        }
        for (int i = 20000; i >= 0; i--) {
            k = k - buckets[i];
            if (k <= 0) {
                return i - 10000;
            }
        }
        return 0;
    }
}