寻找最小成本组合算法

Question

给定一个至少包含 5 项的数组 N，我想找到 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 solution([_, ...n]) {
  n.pop()
  n.sort((a, b) => a - b);

  return n[0] + n[1];
}

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

逻辑与您概述的相同 - 只是使用 JS 提供的一些其他方法。

Answer 2

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)space的解决方案。它还确保索引较小的元素保留在 first 中，以防您需要使用索引并且出于某种原因感兴趣。

算法很清楚，IMO，但是 JS 代码可能不是最好的实现。好久没写JS了

Answer 3

我很确定这是 O(n):

const solution = (arr) => {
  // find smallest that's not at either end
  let idx = 1;
  let P = arr[1];
  for(let i = 2; i < arr.length-1; i++) {
    if(arr[i] < P) {
      idx = i;
      P = arr[i];
    }
  }
  // find second smallest that's not at either end
  let Q = Infinity;
  for(let i = 1; i < arr.length-1; i++) {
    if(i == idx) continue;
    if(arr[i] < Q) Q = arr[i];
  }
  return P + Q;
}

Answer 4

这是在 Python 列表中找到 k 个最小数字的最快方法。其余的都是微不足道的

寻找最小成本组合算法

Find the minimum cost combination algorithm

javascript

arrays

algorithm

performance

time-complexity