モジュロが配列の中で最も反復数を見つけました

Question

誰かが私にこのことがどうやって説明されますか？ここで私は理解しようとしていますコードスニペットは、次のとおりです。

// Iterate though input array, for every element 
    // arr[i], increment arr[arr[i]%k] by k where k is less than of equal to number of elements 
    // ie. k <= n 
    for (int i = 0; i< n; i++) 
     arr[(arr[i]%k)] += k; 

    // Find index of the maximum repeating element 
    int max = arr[0], result = 0; 
    for (int i = 1; i < n; i++) 
    { 
     if (arr[i] > max) 
     { 
      max = arr[i]; 
      result = i; 
     } 
    } 

私たちはアレイを介し拳の時間を繰り返すときに我々

1. たちはモジュロkを繰り返す各要素の値をとることを実現します。
2. これをインデックスとして使用します。
3. インデックスで要素を取り、 をkだけ増やします。

これを実行した後、最高の要素のインデックスが、私たちが探している最も頻繁な番号です。

私は手順を理解していますが、私はそのモジュロとインデックス対値の周りのロジックを理解していません。どんな説明も大歓迎です！

Answer 1

0 <= arr[i] < kまたはarr[i]の範囲がkの値の範囲にあることが保証されている場合にのみ、解決策が機能します。

アルゴリズムは、モジュロ演算を使用していますが、周波数ハッシュマップと同じ配列（arr）を使用して、特定の値の発生数を格納します。除数によって増分されるときは、いつでも同じ残りが与えられます。発生が見つかるたびに、arr[i] % kの要素がkだけインクリメントされます。これは、頻度ハッシュマップを1でインクリメントするのと同様です。繰り返しの最後に、すべての要素が(number of times value occurs) * kだけインクリメントされます。最大要素を見つけると、最も出現する要素が得られます。

あなたが言及していない。このアルゴリズムでは仮定があります

1. 0 < arr[i] <= k
2. k <= n
3. を最も繰り返し要素間のタイがある場合は、最大値を持つ要素が選択されますアップ。
4. (count of occurences) * k + arr[i]がINT_MAXより大きい場合、結果はオーバーフローする可能性があります。