javascript - 寻找最小成本组合算法

Question

给定一个数组 N，其中至少包含 5 个项目，我想找到 2 个数字(P 和 Q)，其中 0 < P < Q < N - 1。

假设我们有以下数组:

const N = [1, 9, 4, 5, 8];

• 如果 P = 1 、Q = 2 ，则成本将为 N[P] + N[Q] = N[1] + N[2] = 9 + 4 = 13<
• 如果 P = 1，Q = 3 ，则成本将为 N[P] + N[Q] = N[1] + N[3] = 9 + 5 = 14<
• 如果 P = 2，Q = 3 ，则成本将为 N[P] + N[Q] = N[2] + N[3] = 4 + 5 = 9<

从这里开始，给出最小成本的组合是 P = 2 和 Q = 3。

这是我找到的解决方案，如果我可以提高其时间复杂度，我正在寻求您的帮助:

function solution(N) {
  // since  0 < P < Q < N - 1
  const sliced = N.slice(1, N.length - 1);
  const sorted = sliced.sort((a, b) => a - b);

  // the minimum should be from the start since we have sorted the array
  const P = 0;
  const Q = 1;

  return getCost(P, Q, sorted);
}

function getCost(P, Q, N) {
  return N[P] + N[Q];
}

// output should be 9
console.log(solution([1, 9, 4, 5, 8]))

在最好的情况下，由于排序的原因，它是 0(n log(n)) ，但我想知道我们是否可以将其改进为例如 O(n) 。

感谢您的帮助

Answer 1

function twoSmallest(arr) {
  let [first, second] = [arr[1], arr[2]]
  
  for (let i = 3; i < arr.length - 1; i++) {
    const el = arr[i]
    if (el < first && el < second) {
      [first, second] = [Math.min(first, second), el] 
    } else if (el < first) {
      [first, second] = [second, el]
    } else if (el < second) {
      second = el
    }
  }
  return first + second
}

这是一个 O(n) 时间和 O(1) 空间解决方案。它还确保索引较小的元素保留在 first 中，以防您需要使用索引并且由于某种原因对它感兴趣。

算法很清楚，IMO，但 JS 代码可能不是最好的实现。我已经有一段时间没有写JS了。