3

我使用 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;
            }
        }
    }
}
4

1 回答 1

3

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

一种简单的可能策略是交错五组，而不是让它们连续。所以，如果向量有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重新排列向量的第一个元素。

于 2014-12-23T19:05:48.483 回答