package question;

import java.util.Random;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question215 {
 public static void main(String[] args) {
 int[] ints = {
 3, 2, 3, 1, 2, 4, 5, 5, 6, 3
 };
 System.out.println(new Question215().findKthLargest(ints, 4));
 }
 public int findKthLargest(int[] nums, int k) {
 return fun(nums, 0, nums.length - 1, k);
 }

 private int fun(int[] nums, int left, int right, int k) {
 int m = partition(nums, left, right);
 if (nums.length-m==k) return nums[m];
 else if (nums.length-m<k) return fun(nums, left, m-1, k);
 else return fun(nums, m+1, right, k);
 }

 private int partition(int[] nums, int left, int right) {
 swap(nums, right, left + new Random().nextInt(right-left+1));
 int m = left;
 while (left<right) {
 if (nums[left]<nums[right]) {
 swap(nums, left, m++);
 }
 left++;
 }
 swap(nums, right, m);
 return m;
 }

 private void swap(int[] nums, int a, int b) {
 int t = nums[a];
 nums[a]=nums[b];
 nums[b]=t;
 }
}