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

- user11138609

---

由于您的数组已经排序，因此您只需要找到i和i + 1之间的差异的最小值，而不是从i + 1到len的所有差异。 diff[index] = Math.abs(arr[i] - arr[i+1]); - gp.

Answer 1

在数组排序后，任意两个元素之间的最小绝对差值必然在相邻的两个元素之间。因此，您可以将嵌套的for循环（O(N^2)）改为单个for循环（O(N)）（尽管sort函数仍然是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个项），因此

原始答案：Original Answer

Math.min(...diff)

会导致

范围错误：超出最大调用堆栈大小

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

}

- CertainPerformance

---

关于 Math.min 的好处和避免不必要的 diff 数组是一个很好的观点。 - gp.

@CertainPerformance...非常感谢您的回复...代码已经可以运行了，而且您的建议对我帮助很大！ - user11138609

你的解释非常清晰，让人能够理解代码。 - user11138609

Answer 2

这是使用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方法，该回调函数将当前值、索引和数组作为参数。

在map方法内部，我们将计算当前数字和下一个数字之间的绝对差异。如果当前迭代的绝对差异小于difference，那么我们在数组中找到了更小的绝对差异。

这一过程一直持续到结束。

- Gasoline and Sauce

---

这个是否超出了数组索引的范围？ - radarbob

@65black...非常感谢您的回复...代码正在运行，您的建议对我帮助很大！而且您的解释很清晰易懂，让我能够理解代码。 - user11138609

Answer 3

  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++;
  }

- gp.

---

@gp...非常感谢您的回复...代码正在运行，您的建议对我帮助很大！您的解释非常清晰易懂，让我能够理解代码。 - user11138609