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

我使用中位数中位数实现了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;
            }
        }
    }
}

最佳答案

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

一种简单的可行策略是交错五个组，而不是使它们连续。因此，如果 vector 具有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)

然后，当找到五个一组的中位数时，将其与组中的第一个元素交换，这意味着中位数的 vector 最终将成为重排 vector 的第一个k元素。