javascript - 效率 : Max difference between two items in a subset of an integer array

Question

我参加了一项编程考试，要求我为特定问题编写高效的代码。我相信我得到了正确的答案(它适用于 5 个测试场景中的 3 个)，但其余两个测试场景(我没有详细说明)由于花费的时间超过 2 秒而失败。

我使用 .slice 和 .apply() 克隆一个子数组并获取其中的最大/最小值。这是最慢的部分吗？我可以做些什么来改进它？

我的代码:

function find_deviation(v, d) {
    var maxMedian = 0;
    var i = 0;
    var len = v.length - d + 1;
    var sequence, min, max, median;
    for(;i < len; ++i) {
        sequence = v.slice(i, i+d);
        min = Math.min.apply(null, sequence);
        max = Math.max.apply(null, sequence);
        median = max - min;
        if(median > maxMedian) {
            maxMedian = median;
        }
    }
    console.log(maxMedian);
}

问题:

数组 v 中长度为 d 的子集中两项之间的最大差异 (maxMedian) 是多少？ v 数组中的所有项都是整数，d 也是如此。

Answer 1

首先，我假设您想在所有大小为 d 的紧凑子数组中找出最大差值是否正确？

如果是这样，那么从我的头顶我可以看到两个问题:

• 数组切片的开销，
• Math.min 和 Math.max 的复杂度为 O(n)，当您执行这两个操作时，复杂度为 O(2n)。

为了解决这两个问题，我提出了以下建议:

function find_deviation(v, d) {
    var maxDifferenceGlobal = 0;
    var len = v.length - d + 1;
    for(var i = 0; i < len; ++i) {
        var min, max;
        if (v[i] <= v[i + 1]) {
            min = v[i]; max = v[i + 1];
        } else {
            max = v[i]; min = v[i + 1];
        }
        for(var j = i + 2; j < i + d; ++j) {
            if (min > v[j]) { min = v[j]; }
            if (max < v[j]) { max = v[j]; }
        }
        var maxDifferenceLocal = Math.abs(max - min);
        if(maxDifferenceLocal > maxDifferenceGlobal) {
            maxDifferenceGlobal = maxDifferenceLocal;
        }
    }
    console.log(maxDifferenceGlobal);
}

这消除了数组切片的开销，并在 O(n) 中找到了 max 和 min，因此仅通过常数更好，但它使得 区别。另外，你不应该使用 Math.abs 来计算差异吗？