java - 我的代码的哪一部分使我的性能受到影响？ (Codility 的 MaxCounter)

Question

我有以下问题:

你有 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)

目标是计算所有操作后每个计数器的值。

写一个函数:

class Solution { public int[] solution(int N, int[] A); } 

给定一个整数 N 和一个由 M 个整数组成的非空零索引数组 A，返回表示计数器值的整数序列。

例如，给定:

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, 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).

可以修改输入数组的元素。

---

我已经使用以下代码回答了这个问题，但尽管具有 O(N+M) 时间复杂度，但只获得了 80% 而不是 100% 的性能:

public class Solution {

    public int[] solution(int N, int[] A) {

        int highestCounter = N;
        int minimumValue = 0;
        int lastMinimumValue = 0;
        int [] answer = new int[N];

        for (int i = 0; i < A.length; i++) {
            int currentCounter = A[i]; 
            int answerEquivalent = currentCounter -1;

            if(currentCounter >0 && currentCounter<=highestCounter){
                answer[answerEquivalent] = answer[answerEquivalent]+1; 

                if(answer[answerEquivalent] > minimumValue){
                    minimumValue = answer[answerEquivalent];
                }
            }

            if (currentCounter == highestCounter +1 && lastMinimumValue!=minimumValue){
                lastMinimumValue = minimumValue;
                Arrays.fill(answer, minimumValue);
            }
        }
        return answer;
    }

}

我的表现哪里有问题？该代码给出了正确的答案，但尽管具有正确的时间复杂度，但并未达到规范。

Answer 1

当您遇到需要 O(N) 的“最大计数器”操作时，不要调用 Arrays.fill(answer, minimumValue);，您应该跟踪由于“最大计数器”操作而分配的最后一个最大值，并在处理完所有操作后仅更新整个数组一次。这需要 O(N+M)。

我将变量名称从 min 更改为 max 以减少混淆。

public class Solution {

    public int[] solution(int N, int[] A) {

        int highestCounter = N;
        int maxValue = 0;
        int lastMaxValue = 0;
        int [] answer = new int[N];

        for (int i = 0; i < A.length; i++) {
            int currentCounter = A[i]; 
            int answerEquivalent = currentCounter -1;

            if(currentCounter >0 && currentCounter<=highestCounter){
                if (answer[answerEquivalent] < lastMaxValue)
                    answer[answerEquivalent] = lastMaxValue +1;
                else 
                    answer[answerEquivalent] = answer[answerEquivalent]+1; 

                if(answer[answerEquivalent] > maxValue){
                    maxValue = answer[answerEquivalent];
                }
            }

            if (currentCounter == highestCounter +1){
                lastMaxValue = maxValue;
            }
        }
        // update all the counters smaller than lastMaxValue
        for (int i = 0; i < answer.length; i++) {
            if (answer[i] < lastMaxValue)
                answer[i] = lastMaxValue;
        }
        return answer;
    }

}