CodeSignal剪丝带算法超时求助：隐藏测试用例超4秒限制

问题背景 #

给定丝带数组a，找出能剪出至少k段的最大丝带长度。当前代码在可见测试用例中运行时长≤0.09秒，但部分隐藏测试用例超时（超过4秒），题目约束长度范围为1到10^9。

原代码 #

function solution(a, k) {
  // the logic here is to determine the biggest size (in length) you can cut the 
  // ribbons(a) into atleast(k) amount of pieces.
  
  // for example a = [1,2,3,4,5]; k = 5 lets use 1 length.
  // 1 - 1 = 0
  // 2 - 1 - 1 = 0
  // 3 - 1 -1 -1 = 0
  // 4 - 1 - 1 -1 -1 = 0
  // 5 - 1 - 1 - 1 -1 -1 = 0, this results in 15 pieces. lets narrow it down with 2
  // 1 - 2 = -1 (this will have to be avoided somehow. for example if a[i] > length)
  // 2 - 2 = 0
  // 3 - 2 = 1 (rule will stop it here thanks to previous example)
  // 4 - 2 -2 = 0
  // 5 - 2 - 2 = 1 (rule will stop it here thanks to previous example)
  //
  // this will result in 6 pieces. can we narrow it down further? lets try 3.
  // we can skip 1 & 2 as the rule will do so too.
  // 3 - 3 = 0
  // 4 - 3 = 1
  // 5 - 3 = 2 this results in 3 pieces. this is not enough pieces. we need a rule in place to invalid this, if the number of pieces is not greater or equal to k.
  
  // we will use a loop test to give us the greatest number, while making a rule that it must be greater than k.
  // then we return the value of test

  let l = 1; // (the length)
  let test = 1000000000;
  let answer;
  while (l < 1000000000) {
    testArr = a.slice();
    let pieces = 0;
    for (i = 0; i < testArr.length; i++) {
      testArr[i] /= l;
      pieces += parseInt(testArr[i]);
    }

    if (pieces < k) {
      l = 1000000000;
    } else {
      if (pieces <= test) {
        test = pieces;
        answer = l;
        console.log(`${l}in for ${pieces} pieces`);
      }
      l++;
    }
  }
  var endTime = performance.now();
  console.log(`it look ${endTime} milliseconds`);
  return answer;
}

超时原因分析 #

1. 线性遍历效率极低：代码从l=1开始逐个递增尝试，直到10^{9。当最大可行长度接近10}9时，循环次数会达到10^9量级，远超4秒时间限制。
2. 不必要的数组拷贝：每次循环执行testArr = a.slice()，产生额外内存开销和时间消耗。
3. 逻辑冗余：修改原数组再计算段数的操作完全多余，直接用原数组计算即可。

优化方案：二分查找法 #

这是典型的最大化最小值问题，二分查找可将时间复杂度降至O(n log(max_len))，其中max_len为数组最大丝带长度，循环次数仅约30次，彻底解决超时问题。

优化后代码 #

function solution(a, k) {
    let left = 1;
    let right = Math.max(...a);
    let answer = 0;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        let totalPieces = 0;

        for (const ribbon of a) {
            totalPieces += Math.floor(ribbon / mid);
            // 提前终止：已满足k段，无需继续计算
            if (totalPieces >= k) break;
        }

        if (totalPieces >= k) {
            // 当前长度可行，尝试更大值
            answer = mid;
            left = mid + 1;
        } else {
            // 当前长度不可行，尝试更小值
            right = mid - 1;
        }
    }

    return answer;
}

优化点说明 #

• 二分查找替代线性遍历：将查找范围限定在1到数组最大丝带长度，每次缩小一半范围，循环次数骤减。
• 移除数组拷贝：直接遍历原数组计算段数，消除不必要的内存操作。
• 提前终止内层循环：计算总段数时，若已达到或超过k，直接跳出循环，减少计算量。
• 使用Math.floor替代parseInt：更直观且避免类型转换潜在问题。

内容的提问来源于stack exchange，提问作者user23333929