本文主要是介绍Q215 数组中第K大的元素,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
思路
可以用排序,但是不用全有序
还有个要求是O(n)
快排改版
快排只排需要的部分
public int findKthLargest(int[] nums, int k) {return quickSort(nums, 0, nums.length-1, nums.length-k);}public static int quickSort(int[] nums, int low, int high, int k){if (low<high){int pivot = partition(nums, low, high);if (pivot == k){return nums[pivot];}else if (pivot > k){return quickSort(nums, low, pivot-1, k);}else {return quickSort(nums, pivot+1, high, k);}}}public static int partition(int[] nums, int low, int high){int pivot = nums[high];while (low<high){while (low<high && nums[low] <= pivot){low++;}nums[high] = nums[low];while (low<high && nums[high] >= pivot){high--;}nums[low] = nums[high];}nums[low] = pivot;return low;}
这篇关于Q215 数组中第K大的元素的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!