BFPRT / Median of Medians Selection Algorithm, O(n) in worst case


  • 0

    While I was reading a solution of Problem 378 Kth Smallest Element in a Sorted Matrix I happened to see @StefanPochmann talking about median of medians, which costs O(n) time even in the worst case. I read the wiki and some other posts and decided to share the idea to you as I think it's a nice solution.

    The algorithm based on quick select. Quick select costs O(n^2) for the worst case (if the search set decreases slowly). This algorithm improves the worst case by decreasing at least 3/10 of the search set in each loop.

    Here are the steps:

    1. Select the pivot(approximate median):
      1.1 Divide the numbers into n/5 groups, with 5 numbers in each group
      1.2 Find the median of each group
      1.3 For the medians in step 1.2, call the BFPRT algorithm to find the median of medians, as the pivot

    2. Split the numbers with the pivot in step 2, put the elements larger than pivot on the left side, and those smaller on the right side

    3. According to the rank of pivot and k, choose the left part or right part to continue finding the Kth largest element.

    Here is my code in js:

    var findKthLargest = function(nums, k) {
        var indexOfKthLargestNum = BFPRT(nums, 0, nums.length-1, k);
        return nums[indexOfKthLargestNum];
    };
    
    //return the index of Kth element
    var BFPRT = function(nums, left, right, k) {
        if (left == right) return left;
        var medianIndex = getMedianIndex(nums, left, right); //index of median of medians
        medianIndex = partition(nums, left, right, medianIndex); //split the numbers and return the new index of median
        var relativeMedianRank = medianIndex - left + 1; //the rank of the median
        if (k == relativeMedianRank) return medianIndex; //median is Kth largest
        else if (k < relativeMedianRank) return BFPRT(nums, left, medianIndex - 1, k); //find the Kth largest between left-medianIndex
        else return BFPRT(nums, medianIndex+1, right, k - relativeMedianRank);
    };
    
    //insert sort and return the index of median
    var insertSort = function(nums, left, right) {
        for (var i=left+1; i<=right; i++) {
            var j = i-1;
            var tmp = nums[i];
            while (nums[j]<tmp && j>=left) {
                nums[j+1] = nums[j];
                j--;
            }
            nums[j+1] = tmp;
        }
        return parseInt((left + (right-left)/2));
    };
    
    //return the index of the median of the numbers
    var getMedianIndex = function(nums, left, right) {
        if (right-left<5) return insertSort(nums, left, right);
    
        var rightBorderOfMedians = left-1;
        for (var i = left; i+4<=right; i+=5) {//every 5 numbers
            var medianIndex = insertSort(nums, i, i+4);
            swap(nums, medianIndex, ++rightBorderOfMedians); //put all medians into the head part of nums so it'll be easier to find median of medians later
        }
        return BFPRT(nums, left, rightBorderOfMedians, parseInt((rightBorderOfMedians-left+1)/2)+1); //find the index of median of medians and return
    };
    
    //split the numbers into 2 parts according to the median, numbers larger than medians will be put at the left part, and those smaller will be put on the right part, return the new index of median after the split
    var partition = function(nums, left, right, medianIndex) {
        var median = nums[medianIndex];
        swap(nums, medianIndex, right); //swap the median and the rightest number, so that no matter how we swap the left part, the median stays at its position, we'll swap the median back to its position later
    
        var divideIndex = left; //divideIndex records the position of split point
        for (var i=left; i<right; i++) {
            if (nums[i]>median) {
                swap(nums, divideIndex, i);
                divideIndex++;
            }
        }
        swap(nums, divideIndex, right); //swap the median back to its position, now its left part are all the numbers larger than it
        return divideIndex;
    };
    
    var swap = function(nums, i, j) {
        var tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.