LintCode 5 · Kth Largest Element.java

	public class Solution {
	/**
	* @param k: An integer
	* @param nums: An array
	* @return: the Kth largest element
	*/
	public int kthLargestElement(int k, int[] nums) {
	// write your code here
	return quickSelect(k, nums, 0, nums.length - 1);
	}
	private int quickSelect(int k, int[] nums, int left, int right) {
	if (left > right) {
	return -1;
	}
	int i = left, j = right;
	int pivot = nums[(left + right) / 2];
	while (i <= j) {
	while (i <= j && nums[i] > pivot) {
	i++;
	}
	while (i <= j && nums[j] < pivot) {
	j--;
	}
	if (i <= j) {
	int tmp = nums[i];
	nums[i] = nums[j];
	nums[j] = tmp;
	i++;
	j--;
	}
	}
	if (left + k - 1 <= j) {
	return quickSelect(k, nums, left, j);
	}
	if (left + k - 1 >= i) {
	return quickSelect(k + left - i, nums, i, right);
	}
	return nums[j + 1];
	}
	}

view raw LintCode 5 · Kth Largest Element.java hosted with ❤ by GitHub