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)，速度不夠快。