javascript - 使用javascript查找数组中任意两对元素之间的最小绝对差时出错

Question

我正在尝试解决一个程序，该程序使用 javascript 查找数组中任何一对元素之间的最小绝对差。输入将参数作为数组元素。输出返回数组中任意两个元素之间的最小绝对差值

比如输入为[1,2,4]，输出为1

问题的详细描述在this中给出。链接。

在我的代码中，当给出包含 1000 个元素的输入数组时，它会编译并显示因超时而终止，但它适用于较小的输入数组

我认为错误来自性能和复杂性方面的问题。我研究了问题，但我仍然不知道如何继续下一步

我的代码:

    var arr = [..] //array containing 1000 elements
    var count = minimumAbsoluteDifference(arr);
    console.log(count);
    function minimumAbsoluteDifference(arr) {
        var diff = []; var index = 0;
        arr.sort((a, b) => { return (a - b); });
        for (var i = 0; i < arr.length-1; i++){
            for (var j = i+1; j < arr.length; j++){
                if (i != j) {
                    diff[index] = Math.abs(arr[i] - arr[j]);
                    console.log("index", i, j);
                    index++;
                }
            }
        }
        var minAbsoluteDifference = Math.min(...diff);
        return minAbsoluteDifference;
    }

Answer 1

数组排序后，任意两个元素之间的最小绝对差必然在两个相邻元素之间。因此，您可以将嵌套的 for 循环 (O(N^2)) 更改为单个 for 循环 (O(N ))(尽管排序函数仍然是O(N log N)，所以整体复杂度只降低到O(N log N)):

function minimumAbsoluteDifference(arr) {
    var diff = [];
    arr.sort((a, b) => a - b);
    for (var i = 0; i < arr.length - 1; i++) {
        if (i < arr.length - 1) {
            diff.push(Math.abs(arr[i] - arr[i + 1]));
        }
    }
    var minAbsoluteDifference = Math.min(...diff);
    return minAbsoluteDifference;
}

这在大多数情况下都有效，但另一个问题是 HackerRank 似乎使用不合理的大数组调用此函数(例如，单个数组中有 100000 个项目)，所以

Math.min(...diff)

会导致

RangeError: Maximum call stack size exceeded

改为在每次迭代时调用 Math.min:

function minimumAbsoluteDifference(arr) {
    var lowestDiff = Infinity;
    arr.sort((a, b) => a - b);
    for (var i = 0; i < arr.length - 1; i++) {
        lowestDiff = Math.min(lowestDiff, Math.abs(arr[i] - arr[i + 1]));
    }
    return lowestDiff;

}