我正在尝试Codility MaxCounter问题:
您将获得N个计数器,这些计数器最初设置为0,并且对其有两种可能的操作:
increase(X) − counter X is increased by 1,
max_counter − all counters are set to the maximum value of any counter.
给出了一个由M个整数组成的非空零索引数组A。该数组表示连续的操作:
if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
if A[K] = N + 1 then operation K is max_counter.
例如,给定整数N = 5且数组A使得:
A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4
每个连续操作后的计数器值将为:
(0, 0, 1, 0, 0)
(0, 0, 1, 1, 0)
(0, 0, 1, 2, 0)
(2, 2, 2, 2, 2)
(3, 2, 2, 2, 2)
(3, 2, 2, 3, 2)
(3, 2, 2, 4, 2)
目的是计算所有操作后每个计数器的值。
例如,给定:
A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4
该函数应返回[3,2,2,4,4,2]。
假使,假设:
N and M are integers within the range [1..100,000];
each element of array A is an integer within the range [1..N + 1].
复杂:
expected worst-case time complexity is O(N+M);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
输入数组的元素可以修改。
这是我的解决方案,为此我使用了reduce方法。它的表现得分为40%。
谁能看到这里的性能问题?
我假设也许是速度降低本身就是问题所在,为了增加该分数,我需要将其转换为for循环,但这在这种情况下使用现代javascript感觉非常难看。
希望你们中的某人会指出与该解决方案无关的一些东西,这些东西不会表明减少是问题,而是表明我是个白痴(我将通过冰镇啤酒来解决这个问题)
function maxCounter(N, A) {
let maxCounter = 0
const NArray = new Array(N).fill(0)
const results = A.reduce((acc, current) => {
if (current === N + 1) return new Array(N).fill(maxCounter)
const out = acc.map((element, index) => {
if (index + 1 === current){
const newValue = element + 1
if (newValue > maxCounter) maxCounter = newValue
return newValue
} else {
return element
}
})
return out
}
, NArray)
return results
}
const results = maxCounter(5, [1,4,2,5,2,6,2])
console.log({results})
最佳答案
您可以引入min
值,如果必须将所有值都设置为max
值,则可以设置该值,但是只有当该值递增时才会发生,然后min
值用于更新,或者最后将所有项分配给至少是min
值。
function maxCounter(n, a) {
var min = 0,
max = 0,
result = [],
i;
for (i of a) {
if (--i === n) {
min = max;
continue;
}
if (!result[i] || result[i] < min) result[i] = min;
if (++result[i] > max) max = result[i];
}
for (i = 0; i < n; i++) {
if (!result[i] || result[i] < min) result[i] = min;
}
return result;
}
console.log(...maxCounter(5, [3, 4, 4, 6, 1, 4, 4]));
console.log(...maxCounter(5, [1, 4, 2, 5, 2, 6, 2]));
关于javascript - Array.reduce的性能,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/59379047/