# Kth Largest Element in an Array

## Question

### Problem Statement

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.

Credits:

Special thanks to @mithmatt for adding this problem and creating all test cases.

## 题解

### Java - 递归求解

public class Solution {
public int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return Integer.MIN_VALUE;
}

int kthLargest = qSort(nums, 0, nums.length - 1, k);
return kthLargest;
}

private int qSort(int[] nums, int left, int right, int k) {
if (left >= right) {
return nums[right];
}

int m = left;
for (int i = left + 1; i <= right; i++) {
if (nums[i] > nums[left]) {
m++;
swap(nums, m, i);
}
}
swap(nums, m, left);

if (k == m + 1) {
return nums[m];
} else if (k > m + 1) {
return qSort(nums, m + 1, right, k);
} else {
return qSort(nums, left, m - 1, k);
}
}

private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}


### Java - 迭代求解

class Solution {
public int findKthLargest(int[] A, int k) {
if (A == null || A.length == 0 || k < 0 || k > A.length) {
return -1;
}

int lo = 0, hi = A.length - 1;
while (lo <= hi) {
int idx = partition(A, lo, hi);
if (idx == k - 1) {
return A[idx];
} else if (idx < k - 1) {
lo = idx + 1;
} else {
hi = idx - 1;
}
}

return -1;
}

private int partition(int[] A, int lo, int hi) {
int pivot = A[lo], i = lo + 1, j = hi;
while (i <= j) {
while (i <= j && A[i] > pivot) {
i++;
}
while (i <= j && A[j] <= pivot) {
j--;
}
if (i < j) {
swap(A, i, j);
}
}
swap(A, lo, j);

return j;
}

private void swap(int[] A, int i, int j) {
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
}


### 源码分析

findKthLargest 里的 while 循环体有种二分搜索的既视感，partition 就是标典型的快排分区写法。