5 · Kth Largest Element - LintCode

# Description

Find the K-th largest element in an array.

Example 1:
Input

k = 1
nums = [1,3,4,2]

Output:

Explanation:
The first largest element is four.

Example 2:
Input:

k = 3
nums = [9,3,2,4,8]

Output:

Explanation:

The third largest largest element is four.

O(n) time, O(1) extra memory.

# Priority Queue

用這個方法的 time complexity = ONlogN

	public int kthLargestElement(int k, int[] nums) {
	Queue<Integer> queue = new PriorityQueue<>();
	for (int i: nums) {
	queue.offer(i);
	if (queue.size() > k) {
	queue.poll();
	}
	}
	return queue.peek();
	}

Time complexity = O(n)
Space = O(1)
用上 quicksort 裡面 partition 的部份

	當while結束後， right 會在左邊，left在右邊
	if (k <= right) {
	return helper(nums, start, right, k);
	}
	if (k >= left) {
	return helper(nums, left, end, k);
	}

	public class Solution {
	/**
	* @param k: An integer
	* @param nums: An array
	* @return: the Kth largest element
	*/
	public int kthLargestElement(int k, int[] nums) {
	return helper(nums, 0, nums.length - 1, nums.length - k);
	}

	public int helper(int[] nums, int start, int end, int k) {
	if (start >= end) return nums[k];

	int left = start, right = end;
	int pivot = nums[start + (end - start) / 2];

	while (left <= right) {
	while (left <= right && nums[left] < pivot) {
	left++;
	}
	while (left <= right && nums[right] > pivot) {
	right--;
	}

	if (left <= right) {
	int temp = nums[left];
	nums[left] = nums[right];
	nums[right] = temp;
	left++;
	right--;
	}
	}
	if (k <= right) {
	return helper(nums, start, right, k);
	}
	if (k >= left) {
	return helper(nums, left, end, k);
	}
	return nums[k];

	}


	}