JS 如何提高这个 Max/Min 编码挑战的性能？

Question

我正在尝试解决一些 'hackerrank.com' 编码挑战。我坚持这个：

您将获得一个整数数组 arr 和一个整数 k。您必须从 arr 的元素创建一个长度为 k 的数组 arr'，以便将其不公平性降至最低。不公平被定义为 max(arr') - min(arr') 函数应该return minimum possible unfairness

我的代码适用于大多数测试用例。然而，在其中三个测试用例中 - arr 和 k 的大小特别大的那些 - 由于超过给定的时间限制而失败。

如何优化代码的性能？提前致谢

function maxMin(k, arr) {
    // create array to push unfairness values to
    var unfairnesses = [];
    // sort given array in ascending order
    arr.sort(function(a, b) {
        return a - b;
    });
    // loop over sorted array    
    for(var i = 0; i < arr.length - k + 1; i++) {
        // get array with the length of k at position i
        var tempArr = arr.slice(i, i + k);
        // determine Max and Min of the sliced array
        var tempArrMax = Math.max(...tempArr);
        var tempArrMin = Math.min(...tempArr);
        // get unfairness of the sliced array
        var thisUnfairness = tempArrMax - tempArrMin;
        // push sliced-array-unfairness to unfairnesses array
        unfairnesses.push(thisUnfairness);
    }

    // return minimal value of unfairnesses array
    return Math.min(...unfairnesses);
}

Answer 1

前两个步骤可以是：

您的数组已排序。因此不需要使用 Math.max 和 Math.min - 切片的第一个元素是最小的，最后一个是最大的。
当您消除 Math.max 和 Math.min 调用时，您可以删除 Array.prototype.slice 调用。然后，您将对数组进行排序和单次传递。

Answer 2

要对数组进行排序，您已经在整个过程中循环了一次。然后你再循环一次，找出哪个是最大的，哪个是最小的。

你循环了两次，因为你只能循环一次：

function minMax(array) {
  const safeArray = array ?? []
  // No max or min as array is empty
  if(safeArray.length === 0) 
    return [undefined, undefined]

  let max: number = Number.MIN_SAFE_INTEGER
  let min: number = Number.MAX_SAFE_INTEGER
  for(let item of safeArray) {
     max = Math.max(item, max)
     min = Math.min(item, min)
  }
  return [max, min]
}

JS 如何提高这个 Max/Min 编码挑战的性能？

JS How can I increase the performance of this Max/Min coding challenge?

javascript

performance