javascript - Medians 空间复杂度的中位数

Question

我使用 Medians of Medians 实现了第 nth_number 选择算法。在 wikipedia ，它指出它的空间复杂度是 O(1)

我必须将中位数存储在一个临时数组中，以便在这些中位数中找到中位数。如果不使用任何额外的内存，您将如何做到这一点？如果不算增加其空间复杂度，请说明。

function nth_number(v, n) {
    var start = 0;
    var end = v.length - 1;
    var targetIndex = n - 1;

    while(true) {

        var medians = []; /* Extra memory. */

        /* Divide our array into groups of 5s. Find a median within each */
        for(var i = start; i <= end; i += 6) {
            if(i + 5 < end)
                medians.push(findMedian(v, i, i + 5));
            else 
                medians.push(findMedian(v, i, end));
        }

        var median = findMedian(medians, 0, medians.length - 1); /* Find the median of all medians */

        var index = partition(v, median, start, end);

        if(index === targetIndex) {
            console.log(median);
            return median;
        }
        else {
            if(index < targetIndex) {
                start = index + 1;
                targetIndex -= index;
            }
            else {
                end = index - 1;
            }
        }
    }
}

Answer 1

选择算法需要重新排列输入向量，因为它进行了一系列分区。因此，可以合理地假设可以重新排列输入向量以找到中位数。

一个简单的可行策略是将五人一组交错排列，而不是让它们连续排列。因此，如果向量有 N == 5K 个元素，则五组为:

(0,   k,    2k,   3k,   4k)
(1,   k+1,  2k+1, 3k+1, 4k+1)
(2,   k+2,  2k+2, 3k+2, 4k+2)
...
(k-1, 2k-1, 3k-1, 4k-1, 5k-1)

然后当你找到一组五个的中位数时，你将它与组中的第一个元素交换，这意味着中位数向量最终将成为前 k 个元素重新排列的向量。