均等に配置されている要素の最大数を確認する方法は？

Question

私は配列を持っていますが、私の目的は、11の倍数のスペースの数を調べることです。配列はソートされません。現在

Such as [27, 16, 52, 84], this would return 2 
     [1, 55, 66, 33] should return 3. 
     [99, 8, 52, 32] should return 0 

私が持っていることは、基本的に配列にするために、各素子を介して実行することである11を乗じて他のすべての要素をチェックしかし、これはO（n²）実行時に私を残し、とにかく私はこれを最適化することができます？

static int eval(int [] a) { 
     int i, j, k, counter = 0; 
     for (i = 0; i < a.length; i++) { 
      for (j = 0; j < a.length; j++) { 
       if (i != j) { 
        for (k = -9; k < 10; k++) { 
         if (a[i] == a[j] + k*11) { 
          counter++; 
          break; 
         } 
        } 
       } 
      } 
     } 
    //if found nothing, will return 0, if found 1 matching, 
    //it should be 2 numbers that share this 11-difference. 
    return counter : counter == 0? 0: counter + 1; 
} 

ありがとうございます！

Answer 1

それは出力が可能になっているものを完全には明らかではありません例えば、[11, 22, 34, 45]のために。私は、サブセットの要素間のすべての差異が11の倍数であり、サイズ-1のサブセットがカウントされない入力の最大サブセットのサイズを求めることとして質問を解釈しています。

同じ剰余mod 11のすべての入力は、11の倍数で区切られているので、入力のうちどれくらいの整数が可能な値のそれぞれがi % 11であるかをカウントする必要があります。これには、入力のサイズに比例した時間がかかります。

static int eval(int[] a) { 
    int[] inputsPerResidue = new int[11]; 
    for (int i : a) { 
     inputsPerResidue[i % 11]++; 
    } 
    int maxGroupSize = 0; 
    for (int groupSize : inputsPerResidue) { 
     if (groupSize > 1 && groupSize > maxGroupSize) { 
      maxGroupSize = groupSize; 
     } 
    } 
    return maxGroupSize; 
} 

Answer 2

これを行うには2つのループが必要です。すべての要素の差を計算し、その数が11の倍数である場合は、カウンタをインクリメントします。あなたは11 2の間の要素の複数を打つかのように、それ以降のループで再び同じ2つの要素を打つことになります、半分カウンターを返します：

static int eval(int [] a) { 
    int counter = 0; 
    for (int i = 0; i < a.length; i++) { 
     for (int j = 0; j < a.length; j++) { 
      if (i != j && Math.abs(a[i] - a[j]) % 11 == 0) { 
       counter++; 
      } 
     } 
    } 
    return counter/2; 
}