代码的哪一部分使性能受到影响？（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

而不是Arrays.fill(answer, minimumValue);每当遇到遇到“ max counter”操作（该操作需要进行调用）时O(N)，都应该跟踪由于“ max counter”操作而分配的最后一个最大值，并在所有操作完成后仅更新一次整个数组。处理。这将花费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;
    }

}