Sorting Problem

Kth Largest In An Array

Problem

Given an array of integers, find the k-th largest number in it.

Example


{
"numbers": [5, 1, 10, 3, 2],
"k": 2
}

and 

{
"numbers": [4, 1, 2, 2, 3],
"k": 4
}


Output:

5 and 2 

Solution


function swap(numbers, i, j) {
    let tmp = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = tmp;
}

function quickSelect(numbers, left, right, k) {
    let le = left;
    let ri = right;
    let mid = numbers[right];
    while (le < ri) {
        if (numbers[le++] > mid) swap(numbers, --le, --ri);
    }
    swap(numbers, le, right);
    let len = right - le;
    if (len === k - 1) return numbers[le];
    else if (len < k - 1) return quickSelect(numbers, left, le - 1, k - len - 1);
    else return quickSelect(numbers, le + 1, right, k);
};

function findKthLargest(numbers, k) {
    return quickSelect(numbers, 0, numbers.length - 1, k);
};

//Input [5, 1, 10, 3, 2] Output: 5
//Input [4, 1, 2, 2, 3] Output: 2
const result = findKthLargest([4, 1, 2, 2, 3], 4)
console.log(result);

Leave a comment