MaxCounters codilityの理解

Question

私はCodi​​lityについていくつかの課題を試してみたかったのですが、始めから始めました。すべての割り当ては、MaxCountersと呼ばれるものまで比較的簡単でした。私はこれが特に難しいとは思わないが、最初は痛みがないとマークされている。

私はtaskを読み、C＃言語でコーディングし始めている：もちろんの3つのループを持つ

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; 
} 

はそれが本当に遅くなりますが、後でそれを残すことができます。私の懸念は、このようにこのことを理解し、他のすべての人々がこの質問で好きに見える方法です。here。

割り当ての説明から。

それは2つのアクションがあります

• 増加（X） - カウンタXは、1だけ増加
• 最大カウンタである - すべてのカウンタは、任意 カウンタの最大値に設定されています。条件下で起こる

：

• もしそのような[K] = X、その1≤X≤N、動作Kが増加である（X）、
• なら[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; 
} 

このコードはCodi​​lity 100％となります。

質問：

私は著者がresult[A[K] - 1]を使用するタスクから知っていたか知りたいのですが？ resetLimitは何を表しますか？

多分私は私の英語のために質問が完全に誤解されています。私はちょうどそれを越えることはできません。

EDIT：私のコード提供に基づき

、どのように私は割り当てを誤解したのですか？一般的に私は問題の説明を求めています。何が行われる必要があるかを説明するか、コードを正しい結果として取り上げて説明し、なぜこのようにするのか説明してください。

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の操作に起因して更新されなければならないかどうかを調べ、彼は

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

彼の解決策が実行されている。このカウンターの上に実行されなかったすべてのmax counter操作を補いますO(n)と十分に速いです。