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

Question

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

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

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

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

我认为错误来自性能和复杂性方面的问题。我研究了问题，但我仍然坚持如何进一步的步骤

我的代码：

    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：超出最大调用堆栈大小

改为在每次迭代时调用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;

}

Answer 2

  for (var i = 0; i < arr.length - 1; i++) {
      var j = i+1;//only check the diff with next neighbor
      diff[index] = Math.abs(arr[i] - arr[j]);
      console.log("index", i, j);
      index++;
  }

Answer 3

这是使用Array.map方法的好机会，因为它允许我们访问正在迭代的currentValue，迭代的索引以及我们当前正在减少的数组。这是函数的外观：

function minimumAbsoluteDifference(array) {
  const sortedArray = [...array].sort((a, b) => a - b);
  let difference = sortedArray[sortedArray.length - 1];

  sortedArray.map((currentValue, index, array) => {
    const currentMinDifference = Math.abs(currentValue - array[index + 1]);

    if (currentMinDifference < difference) {
      difference = currentMinDifference;
    }
  });

  return difference;
}

首先，我们对数组进行排序以使其更易于使用，然后我们将差异初始化为数组中的最大项。

然后我们使用提供的回调调用排序数组上的map方法，将currentValue，index和array作为参数。

在map方法中，我们将计算当前数字与下一个数字之间的绝对差异。如果当前迭代的绝对差值小于difference，那么我们发现阵列中的绝对差异较小。

这一直持续到最后。