c# - MaxCounters codility 理解

Question

我想在 Codility 上尝试一些挑战，并从头开始。所有作业都相对容易，直到名为 MaxCounters 的作业为止。我不认为这个特别难，尽管它是第一个标记为非无痛的。

我已阅读task并开始使用 C# 语言编写代码:

public static int[] maxPart(int N, int[] A){
    int[] counters = new int[N];
    for(int i = 0; i < A.Length; i++){
        for(int j = 0; j < counters.Length; j++){
            if(A[i] == counters[j] && (counters[j] >= 1 && counters[j] <= N )){
                counters [j] = counters [j] + 1;
            }
            if(A[i] == N + 1 ){
                int tmpMax = counters.Max ();
                for(int h = 0; h < counters.Length; h++){
                    counters [h] = tmpMax;
                }
            }
        }
    }
    return counters;
}

当然，有 3 个循环会使它变得非常慢，但让我们稍后再说。我关心的是我是如何理解这个问题的，而其他人在这个问题上的看法是这样的here .

来自作业的描述。

它有两个 Action :

• increase(X) - 计数器 X 增加 1，
• max counter - 所有计数器都设置为任何一个的最大值柜台。

在以下条件下发生:

• 如果 A[K] = X，使得 1 ≤ X ≤ N，则操作 K 为 increase(X)，
• 如果 A[K] = N + 1 则操作 K 是最大计数器。

这两个条件都在上面的代码中说明。显然这是错误的，但我很困惑，我不知道我怎么能理解得不一样。

为什么这段代码是错误的，我在任务描述中遗漏了什么？

评分最高的答案之一如下所示:

public int[] solution(int N, int[] A) {
    int[] result = new int[N];
    int maximum = 0;
    int resetLimit = 0;

    for (int K = 0; K < A.Length; K++)
    {
        if (A[K] < 1 || A[K] > N + 1)
            throw new InvalidOperationException();

        if (A[K] >= 1 && A[K] <= N)
        {
            if (result[A[K] - 1] < resetLimit) {
                result[A[K] - 1] = resetLimit + 1;
            } else {
                result[A[K] - 1]++;
            }

            if (result[A[K] - 1] > maximum)
            {
                maximum = result[A[K] - 1];
            }
        }
        else
        {
            // inefficiency here
            //for (int i = 0; i < result.Length; i++)
            //    result[i] = maximum;
            resetLimit = maximum;
        }
    }

    for (int i = 0; i < result.Length; i++)
        result[i] = Math.max(resetLimit, result[i]);

    return result;
}

此代码的 Codility 为 100%。

问题:

想知道作者是怎么从任务中知道使用result[A[K] - 1]的？ resetLimit 代表什么？

也许我不确定我的英语完全误解了这个问题。我就是不能过去。

编辑:

根据我提供的代码，我是如何误解作业的？一般来说，我要求对问题进行解释。是说明需要做什么，还是把代码作为正确的结果，并提供和解释为什么这样做？

Answer 1

在我看来，您以某种方式混合了计数器的索引(A 中的值)和计数器的值(counter 中的值)。所以使用 A[i]-1 没有什么神奇之处——它是问题描述中的值 X(调整为基于 0 的索引)。

我天真的方法是，我理解问题的方式(我希望它清楚，你的代码做错了什么):

public static int[] maxPart(int N, int[] A){
    int[] counters = new int[N];
    for(int i = 0; i < A.Length; i++){
        int X=A[i];
        if(X>=1 && X<=N){ // this encodes increment(X), with X=A[i] 
             counters [X-1] = counters [X-1] + 1; //-1, because our index is 0-based  
         }
         if(X == N + 1 ){// this encodes setting all counters to the max value
             int tmpMax = counters.Max ();
             for(int h = 0; h < counters.Length; h++){
                    counters [h] = tmpMax;
                }
            }
        }
    }
    return counters;
}

显然，这太慢了，因为复杂度为 O(n^2)，操作次数为 n=10^5(数组长度 A)，在如下操作顺序的情况下:

max counter, max counter, max counter, ....

评价最高的解决方案以惰性方式解决问题，不会在每次遇到 max counter 操作时显式更新所有值，而只是记住此操作后所有计数器必须具有的最小值在 resetLimit 中。因此，每次他必须递增一个计数器时，他会检查它的值是否必须由于以前的 max counter 操作而更新，并弥补他没有进行的所有 max counter 操作。 t 在这个计数器上执行

if(result[A[K] - 1] < resetLimit) {
                result[A[K] - 1] = resetLimit + 1;
            }

他的解决方案在 O(n) 中运行并且足够快。