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));

8 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
  6. Many individuals who are thinking about pursuing their career in the entertainment and technology work, would find the game designing very engaging thing for them. Click for montreal to play online casino now. This industry is seeing new aspiring game designers.

    ReplyDelete
  7. Adsorbent Resin for Adsorption refining of stevioside - Alfa Chemistry focuses on the development and manufacture of various ion exchange resin products, including various cation exchange resins, anion exchange resins, mixed bed resins, adsorption resins, nuclear grade resins, and so on.

    ReplyDelete
  8. TAMRA-PEG4-DBCO for sale - Alfa Chemistry provides you with a complete range of high quality photochemistry related products. It is the preferred partner of many universities, research institutions and non-profit organizations.

    ReplyDelete

Blogroll

Popular Posts