LeetCode215数组中第K个最大元素

题目描述

  给定整数数组 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;}
}