Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,Given [3,2,1,5,6,4] and k = 2, return 5.
Note: You may assume k is always valid, 1 ≤ k ≤ array’s length.
Solution:
Introduction to Algorithm, there was one step in quickselect — partition,
public int findKthLargest(int[] nums, int k) {return findK(nums, nums.length-k, 0, nums.length-1);}public int findK(int[] nums, int k, int s, int e) {if(s>=e) return nums[s];int m = partition(nums, s, e);if(m == k) return nums[m];else if(m<k) {return findK(nums, k, m+1, e);}else {return findK(nums, k, s, m-1);}}public int partition(int[] nums, int i, int j) {int pivot = nums[i];int m = i;int n = i+1;while(n<=j) {if(nums[n]<pivot){swap(nums, ++m, n);}n++;}swap(nums, i,m);return m;}public void swap(int[] nums, int a, int b) {int temp = nums[a];nums[a] = nums[b];nums[b] = temp;}
版权声明:本文为博主原创文章,未经博主允许不得转载。
,接受自己的失败面,是一种成熟,更是一种睿智;