# Kth Largest Element

``````给出数组[9,3,2,4,8]，第三大的元素是4

``````

``````你可以交换数组中的元素的位置
``````

``````要求时间复杂度为O(n），空间复杂度为O(1）
``````

## Solution

Quickselect uses the same overall approach as quicksort, choosing one element as a pivot and partitioning the data in two based on the pivot, accordingly as less than or greater than the pivot. However, instead of recursing into both sides, as in quicksort, quickselect only recurses into one side – the side with the element it is searching for. This reduces the average complexity from O(n log n) (in quicksort) to O(n) (in quickselect).

1. 第8行 `Kth largest element = len-K+1` th smallest element

2. 第24行，l、r在相遇之后，l 所处的位置就是第一个大于等于pivot元素所在位置，把它跟pivot交换，pivot就放在了它应该在的位置

## Complexity

1. sort O(nlogn)
2. quickselect O(n)

## Code

``````class Solution {
//param k : description of k
//param numbers : array of numbers
//return: description of return
public int kthLargestElement(int k, ArrayList<Integer> numbers) {
if (k > numbers.size())
return 0;
return helper(numbers.size()-k+1, numbers, 0, numbers.size()-1);
}

public int helper(int k, ArrayList<Integer> numbers, int start, int end) {
int l=start, r=end;
int pivot = end;
while (true) {
while (numbers.get(l)<numbers.get(pivot) && l<r) {
l++;
}
while (numbers.get(r)>=numbers.get(pivot) && l<r) {
r--;
}
if (l == r) break;
swap(numbers, l, r);
}
swap(numbers, l, end);  // l here is the first one which is bigger than pivot, swap it with the pivot
if (l+1 == k) return numbers.get(l);
else if (l+1 < k) return helper(k, numbers, l+1, end);
else return helper(k, numbers, start, l-1);
}

public void swap(ArrayList<Integer> numbers, int l, int r) {
int temp = numbers.get(l);
numbers.set(l, numbers.get(r).intValue());
numbers.set(r, temp);
}
};
``````