Problem

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. k is always valid, 1 ≤ k ≤ array's length.

Example

given [3,2,1,5,6,4] and k = 2, return 5.

JavaScript Code

function findKthLargest(nums, k) {
    if (k < 1 || nums == null) {
        return 0;
    }
    return getKth(nums.length - k +1, nums, 0, nums.length - 1);
}
 
function getKth(k, nums, start, end) {
 
    var pivot = nums[end];
 
    var left = start;
    var right = end;
 
    while (true) {
 
        while (nums[left] < pivot && left < right) {
            left++;
        }
 
        while (nums[right] >= pivot && right > left) {
            right--;
        }
 
        if (left == right) {
            break;
        }
 
        swap(nums, left, right);
    }
 
    swap(nums, left, end);
 
    if (k == left + 1) {
        return pivot;
    } else if (k < left + 1) {
        return getKth(k, nums, start, left - 1);
    } else {
        return getKth(k, nums, left + 1, end);
    }
}
 
function swap(nums, n1, n2) {
    var tmp = nums[n1];
    nums[n1] = nums[n2];
    nums[n2] = tmp;
}

console.log(findKthLargest([1,2,5,3,7,4],2));

5 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. Find Kth largest element in array using java script. Code which is just use in the script is now be perfect sometime you decide to find professional cv writing service reviews but if error was found in the script code means whole array is waste and you cannot understand and also not use it for you.

    ReplyDelete
  3. Section 2 of the period to be daring is demonstrating you the ever the fascinating material. I realize that everything which is as indicated by the portland printers is simply should be done straightforwardly. Individuals attempting to show intrigue however not this time this could be occur.

    ReplyDelete
  4. Site connection of the page is simply here. In the event that you think from this west linn aesthetics site you just not discover something helping now you have consent to proceed onward the other site where you can without much of a stretch discover helping thing for you. What's more, that is great ever for you in when you think about it.

    ReplyDelete
  5. TCM blog entry detail design is here infront of you. In the event that you need to comprehend this detail, at that point here is a public speaking coach chance for you which educate you regarding the design strategy and something more which is essential for you in this time.

    ReplyDelete

Blogroll

Follow this blog by Email

Popular Posts