javascript - 有没有办法改进此代码以避免大型数组超时？

Question

我正在处理这个问题:https://www.hackerrank.com/challenges/fraudulent-activity-notifications/

我的代码几乎可以正常工作，但对于某些测试用例它会失败，因为数组很大(超过 200000 项)。我花了几个小时试图了解我可以做些什么来提高速度，但我无法提出一个可行的解决方案，所以我的 2 个测试总是因超时而失败，我很沮丧试图通过这个测试。我想我无法避免第一个循环和排序中的循环，但想不出更快的方法。

网站描述的问题是这样的:

HackerLand National Bank 有一个简单的政策来警告客户可能的欺诈账户事件。如果客户在某一天花费的金额大于或等于客户连续几天的花费中位数，他们会向客户发送有关潜在欺诈的通知。银行不会向客户发送任何通知，直到他们至少拥有该数量的前几天交易数据。

我用这段代码解决了

function getMedianNumber(arr) {
  arr.sort((a, b) => a - b);

  let medianNumber = 0;
  const middle = Math.floor(arr.length / 2);

  if (arr.length % 2 === 0) {
    // Is even we get the median number
    medianNumber = (arr[middle] + arr[middle - 1]) / 2;
  } else {
    const index = Math.floor(middle);
    medianNumber = arr[index];
  }

  return medianNumber;
}

function activityNotifications(expenditure, d) {
  let notifications = 0;
  let len = expenditure.length - 1;

  for (let i = len; i > d - 1; i--) {
    let trailingDays = expenditure.slice(i - d, i);
    let dayExpense = expenditure[i];
    let median = getMedianNumber(trailingDays);

    if (expenditure[i] >= median * 2) {
      notifications++;
    }
  }

  return notifications;
}

它只在 2 个测试用例中失败，因为传递的数组很大并且出现超时错误。

Answer 1

expenditure.slice(i - d, i); 太昂贵了，您通过在每次迭代中复制数组元素使其成为 O(n^2)。使用原始数组的索引计算中位数:getMedianNumber(arr, startIndex, endIndex)。