[leetcode] Kth Largest Element in an Array

用Quick Select...其实可以在原array上修改...不过可能code会复杂点。。 直接straight forward 建立新array做

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

public class Solution { public int findKthLargest(int[] nums, int k) { List<Integer> numsList = new LinkedList<Integer>(); for (int i = 0; i < nums.length; i++) numsList.add(nums[i]); return findKthRec(numsList, k); } private int findKthRec(List<Integer> nums, int k){ int pivot = nums.get(0); int numPivot = 0; LinkedList<Integer> left = new LinkedList<Integer>(); LinkedList<Integer> right = new LinkedList<Integer>(); while (!nums.isEmpty()){ int current = nums.remove(0); if (current < pivot) right.add(current); else if (current > pivot) left.add(current); else numPivot++; } if (left.size() >= k) return findKthRec(left, k); else if (left.size()+numPivot >= k) return pivot; return findKthRec(right, k-left.size()-numPivot); } }