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.
解题思路：我采用的排序方法，然后从排序后的数组中取出对应的值就好。 public class Solution { public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length-k]; } } 这样的语句太简单了，就在网上找了一下分治法的解法，发现了一篇不错的博客 点击打开链接，看了之后也自己动手敲了一下。 public class Solution { public int findKthLargest(int[] nums, int k) { int left=0; int right=nums.length-1; while(true){ int pos = helper(nums,left,right); if(pos==k-1){ return nums[pos]; }else if(pos< k-1){ left=pos+1; }else{ right=pos-1; } } } public int helper(int[] nums,int begin ,int end ){ int left = begin +1; int right = end; while(left <=right){ if(nums[left]<nums[begin] && nums[right]>nums[begin]){ swap(nums,left,right); } if(nums[left]>=nums[begin]){ left++; } if(nums[right]<=nums[begin]){ right--; } } swap(nums,begin,right); return right; } public void swap(int[] nums, int i,int j){ int temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } }