int paratition(int *A, int p, int r) {
    int x = A[r];
    int i = p - 1;
    
    int tmp;
    for(int j = p; j < r; ++ j) {
        if(A[j] >= x) {
            ++ i;
            tmp  = A[i];
            A[i] = A[j];
            A[j] =  tmp;
        }
    }
    ++ i;
    tmp  = A[i];
    A[i] = A[r];
    A[r] =  tmp;
    return i;
}

int random_paratition(int *A, int p, int r) {
    int i = rand() %(r - p + 1) + p;
    int tmp;
    
    tmp  = A[i];
    A[i] = A[r];
    A[r] =  tmp;
    return paratition(A, p, r);
}

int helper(int* A, int p, int r, int i) {
    if(r == p) return A[p];
    int q = random_paratition(A, p, r);
    int k = q - p + 1;
    
    if(i == k)
        return A[q];
    if(i <  k)
        return helper(A, p, q - 1, i);
    else
        return helper(A, q + 1, r, i - k);
}

int findKthLargest(int* nums, int numsSize, int k) {
    srand(1311);
    return helper(nums, 0, numsSize - 1, k);
}