Wie überprüft man die maximale Anzahl von Elementen, die gleichmäßig verteilt sind?

Question

Ich habe ein Array und mein Ziel ist herauszufinden, wie viele um ein Vielfaches von 11 sind. Das Array ist nicht sortiert.

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

Zeit, was ich habe, ist im Grunde in dem Array für-jedes Element zu durchlaufen, überprüfen jedes andere Element mit mit 11 multipliziert Aber das lässt mich an einem O (n²) Laufzeit, trotzdem kann ich das optimieren ?

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

Vielen Dank!

Answer 1

Es ist nicht ganz klar, was die Ausgabe sein soll zum Beispiel, [11, 22, 34, 45]. Ich interpretiere die Frage so, dass ich nach der Größe der größten Teilmenge der Eingabe frage, wobei alle Unterschiede zwischen Elementen der Teilmenge ein Vielfaches von 11 sind und wobei Teilmengen der Größe 1 nicht zählen.

Alle Eingänge mit dem gleichen Restmodul 11 ​​sind um ein Vielfaches von 11 voneinander getrennt, so dass wir nur zählen müssen, wie viele Eingänge im Eingang einen möglichen Wert von i % 11 haben. Dies erfordert eine lineare Zeit in der Größe der Eingabe.

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

Sie würden 2 Schleifen benötigen, um dies zu erreichen. Berechnen Sie den Unterschied zwischen jedem Element, und wenn diese Zahl ein Vielfaches von 11 ist, erhöhen Sie den Zähler. Rück Hälfte der Zähler, als ob Sie ein Vielfaches von 11 zwischen zwei Elementen treffen, werden Sie am Ende schlagen die beiden gleichen Elemente wieder später in der Schleife:

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