MaxCounters（codility 中的第 4 课）- 100% 正确性，但效率为 60%，为什么？

Question

问题链接

简而言之：

• N

  是一个整数，代表计数器的数量和允许的最大计数器；

• A

  是一个数组，表示在特定计数器上完成的操作（例如，如果

  A[0]

  是

  1

  并且

  N

  是

  3

  ，我们需要将

  1

  添加到

  counter[0]

  ）；
• 如果

  A

  中的某个元素是

  N+1

  ，则

  counter

  中的所有元素都应更改为

  counter

  数组中最大的数字。

我提交了我写的代码，性能只有 60%。这是为什么？下次我应该采取什么方法来解决问题以提高效率？我该如何改进？

function solution(N,A){

    let counters = Array(N).fill(0);
    let maxCounter = 0;
    for(i=0;i<A.length;i++){
        if(A[i]<=N){
            counters[A[i]-1]++
            if(counters[A[i]-1]>maxCounter){maxCounter = counters[A[i]-1]};
        }
        else if(A[i]===N+1){
            counters = Array(N).fill(maxCounter)
        }
    }
    return counters
}

编辑：我不知道这个网站不是为了解决有关代码改进的问题，谢谢，我会在其他地方问。

Answer 1

效率的

60%

分数是因为最后两个测试用例执行了超过

10,000

“最大计数器”操作。 https://app.codility.com/demo/results/trainingA86B4F-NDB/

每个操作都必须迭代

counter

数组，该数组可能有多达

100,000

个元素。总共有

1 billion

次写入，因此性能问题的原因很快就能显现出来。

为了改进这一点并降低这个数字，我们可以消除不必要的连续 “最大计数器” 操作，例如，引入一个标志来表示

counter

数组是否已达到最大值并且无需迭代它一切从头再来。

示例代码：

const solution = (n, arr) => {
  const counter = new Array(n).fill(0);
  let max = 0, counterMaxed = false;

  for (let curr of arr) {
    if (curr > n) {
      if (!counterMaxed) { counter.fill(max); counterMaxed = true; }
      continue;
    }

    curr--; counter[curr]++; counterMaxed = false;
    if (counter[curr] > max) { max = counter[curr]; }
  }

  return counter;
};

这会得到直

100%

分数：
https://app.codility.com/demo/results/training3H48RM-6EG/

Answer 2

一个可能的改进是，当您需要用新的最大计数器填充整个数组时，不要创建一个全新的数组来执行此操作 - 相反，更改现有数组。

else if(A[i]===N+1){
    counters.fill(maxCounter)
}

如果有很多计数器，这可能会产生很大的影响。

Answer 3

这是一个使用对象的解决方案，它将仅生成一次实际数组（在应用所有操作之后）。

“跟踪器”对象将仅保存那些进行操作的计数器的索引和值。假设 N（即计数器的“num”数量）为 50,000，但只有 5,000 个计数器在 A（即“arr”数组）中进行显式操作，只有这 5,000 个元素将被tracked（使用“tracker”对象） ).

代码片段

// alternative solution using object
const counterOps = (num, arr) => {
  // the "tracker" object we will use to populate the result array
  const tracker = {};
  
  // when "num+1" to reset all elements to "max", then
  // the "max" value is stored in "lastMaxSet"
  let lastMaxSet = 0;
  
  // helper method to get current max from "tracker"
  const getMax = obj => Math.max(...Object.values(obj));
  
  // helper method to "set" "all" values to "max"
  const setMax = obj => {
    lastMaxSet = getMax(obj);
    Object.keys(obj).forEach(k => obj[k] = lastMaxSet);
  };
  
  // iterate through "arr" and "apply" each "operation"
  arr.forEach(elt => {
    if (elt === num + 1) {
      // "reset to max" operation is applied
      setMax(tracker);
    } else {
      // a particular counter is incremented
      const k = elt - 1;
      tracker[k] ??= lastMaxSet;
      tracker[k]++;
    }
  });
  
  // the "tracker" object is used to generate
  // the result-array on-the-fly
  return [...Array(num).fill(lastMaxSet)].map(
    (val, idx) => idx in tracker ? tracker[idx] : val
  );
};

console.log(counterOps(5, [3, 4, 4, 6, 1, 4, 4]));

.as-console-wrapper { max-height: 100% !important; top: 0 }

请尝试并分享反馈，如果它有帮助（与性能）。

Answer 4

这是我的C#解决方案，我得分100%

public int[] solution(int N, int[] A) {
    // Implement your solution here
    int[] counters = new int[N];
    int max = 0;
    int lastMaxReach = 0;
    for(int i=0;i<A.Length;i++){
        int current = A[i];
        if(current>=1 && current<=N){
            if(lastMaxReach > 0 && counters[current-1]<lastMaxReach){
                counters[current-1] = lastMaxReach;
            }
            counters[current-1] += 1;
            if(counters[current-1] > max){
                max = counters[current-1];
            }
        }else if(current == N+1){
            lastMaxReach = max;
        }
    }

    for(int i=0;i<counters.Length;i++){
        if(lastMaxReach > 0 && counters[i]<lastMaxReach){
            counters[i] = lastMaxReach;
        }
    }
    return counters;
}