我正在尝试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/

10-10 17:33