package LeetCode;

import java.util.ArrayList;

public class LC_215_wrong {
    static ArrayList<Integer> res = new ArrayList<>();

    public static void main(String[] args) {
        findKthLargest(new int[]{2,1}, 2);
    }

    public static int findKthLargest(int[] nums, int k) {
        if (nums.length == 1) return nums[0];
        quicksort(nums, 0, nums.length - 1, k);
        int tmp = res.get(0);
        res.clear();
        return tmp;
    }

    public static void quicksort(int[] arr, int low, int high, int k) {
        if (res.size() == 1) return;
        if (low < high) {
            int pos = part(arr, low, high, k);
            quicksort(arr, low, pos - 1, k);
            quicksort(arr, pos + 1, high, k);
        }
    }

    public static int part(int[] arr, int low, int high, int k) {
        int pivot = arr[low];
        while (low < high) {
            while (arr[high] >= pivot && low < high) high--;
            arr[low] = arr[high];
            while (arr[low] <= pivot && low < high) low++;
            arr[high] = arr[low];
        }
        arr[low] = pivot;
        if (low == arr.length - k) res.add(arr[low]);
        return low;
    }
}