MaxCounters编码理解

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。

来自作业的说明。

它有2个操作：

• 增加（X） - 计数器X增加1，
• 最大值计数器 - 所有计数器被设置为任何 计数器的最大值。

条件下发生：

• 如果A [K] = X，使得1≤X≤N，则操作K是增加（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操作，他并没有在这个柜台

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

他的解决方案运行在执行O(n)，速度不够快。