Find Kth Largest Element In Array Using JavaScript

Sunday, 14 June 2015 | Posted by

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));
Labels:,,

5 comments:

  1. Unknown19 November 2015 at 09:29

    This comment has been removed by the author.

    ReplyDelete
  2. unknown21 April 2020 at 04:16

    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. james15 May 2020 at 22:44

    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. james15 May 2020 at 22:45

    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. james15 May 2020 at 22:45

    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

Subscribe to: Post Comments (Atom)

Blogroll

Follow this blog by Email

Popular Posts