Collect Indizes von Duplikaten Werte in 2D-Int-Array-Algorithmus

Question

Ich arbeite an Spielautomaten und stand vor dem Problem der Ergebnisse zu sammeln. Frage ist, was ist der schnellste Ansatz, um Indizes von doppelten Werten im 2D-int-Array zu sammeln? Bedingung ist hier nur idexes von Werten zu sammeln, die auftreten 5 mal

CASE 1

Eingang (erhalten Indizes von Wert only):

int[][] input = new int[][]{ 
      new int[]{1, 2, 3, 4, 8}, 
      new int[]{6, 3, 2, 3, 5}, 
      new int[]{3, 9, 7, 1, 3} 
    }; 

erwartete Ausgabe:

[2, 1, 0, 1, 2] 

CASE 2

Eingang (erhalten Indizes von und Werte nur):

int[][] input = new int[][]{ 
      new int[]{1, 5, 3, 5, 8}, 
      new int[]{5, 3, 5, 3, 5}, 
      new int[]{3, 9, 7, 1, 3} 
    }; 

erwartete Ausgabe:

[2, 1, 0, 1, 2] //for 3 value 
[1, 0, 1, 0, 1] //for 5 value 

meine Lösung (seine sehr schlecht)

1) sammeln Duplikate (diese nicht für CASE Arbeits 2)

Map<Integer, Integer> amountMap = new HashMap<>(); 
for (int[] row : railSpin) { 
    for (int value : row) { 
     amountMap.put(value, amountMap.containsKey(value) ? amountMap.get(value) + 1 : 1); 
    } 
} 

2) entfernen nicht 5 Spiele

if (amountMap.containsValue(5)) { 
    Iterator<Integer> amountIterator = amountMap.values().iterator(); 
    while (amountIterator.hasNext()) { 
     if (amountIterator.next() != 5) { 
      amountIterator.remove(); 
     } 
    } 
} 

3) iterieren Kopf nach unten und sammeln Indizes

List<Integer> indexes = new ArrayList<>(); 
for (int row = 0; row < 5; row++) { 
    for (int col = 0; col < railSpin.length; col++) { 
     int valueToCheck = railSpin[col][row]; 
     if (amountMap.keySet().contains(valueToCheck)) { 
      indexes.add(col); 
     } 
    } 
} 

4) Split-Array bei Bedarf

List<List<Integer>> splitResults = new ArrayList<>(); 
for (int start = 0; start < indexes.size(); start += 5) { 
    int end = Math.min(start + 5, indexes.size()); 
    List<Integer> sublist = indexes.subList(start, end); 
    splitResults.add(new ArrayList<>()); 
    splitResults.get(start /5).addAll(sublist); 
} 

Können Sie eine Lösung ohne so viele Iterationen vorschlagen, die für CASE 2 geeignet wäre? Ich glaube in Kraft der Stackoverflow

Answer 1

zählen, wie ich würde es tun:

1. Iterate über die gesamte Tabelle ONCE, um eine Karte von Indizes
2. Entfernen Sie alle Eintrag, der

EDIT nicht 5 gültige Indizes hat zu erstellen: Ich wechselte mit Arraylist zu arbeiten, weil es einfach besser ist:

Code:

public static void main(String t[]) throws IOException { 
    int[][] input1 = new int[][] { 
     new int[] { 1, 2, 3, 4, 8 }, 
     new int[] { 6, 3, 2, 3, 5 }, 
     new int[] { 3, 9, 7, 1, 3 } }; 

    int[][] input2 = new int[][] { 
     new int[] { 1, 5, 3, 5, 8 }, 
     new int[] { 5, 3, 5, 3, 5 }, 
     new int[] { 3, 9, 7, 1, 3 } }; 

    System.out.println("case 1"); 
    doWith(input1); 
    System.out.println("case 2"); 
    doWith(input2); 
} 

public static void doWith(int[][] table){ 
    Map<Integer, List<Integer>> allIndexes = getAllIndexes(table); 
    /* Java 8 style 
    Map<Integer, List<Integer>> fiveOccurrencesIndexes = allIndexes.entrySet().stream() 
      .filter(e ->e.getValue().size() == ROW_SIZE) 
      .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue)); 
      */ 
    Map<Integer, List<Integer>> fiveOccurrencesIndexes = new HashMap<Integer,List<Integer>>(); 
    for(Map.Entry<Integer,List<Integer>> entry : allIndexes.entrySet()){ 
     if(entry.getValue().size() == ROW_SIZE){ 
      fiveOccurrencesIndexes.put(entry.getKey(), entry.getValue()); 
     } 
    } 

    fiveOccurrencesIndexes.entrySet().forEach(e -> System.out.println(e.getKey()+ " : "+e.getValue())); 
} 

// Map of indexes per value 
public static Map<Integer,List<Integer>> getAllIndexes(int[][] table){ 
    Map<Integer,List<Integer>> result = new HashMap<>(); 
    // we should force minValue < maxValue 
    for(int i=0; i<ROW_SIZE; i++){ 
     for(int j=0;j<COL_SIZE; j++){ 
      Integer value = table[j][i]; 
      if(!result.containsKey(value)){ 
       List<Integer> indexes = new ArrayList<>(); // init value 
       result.put(value, indexes); 
      } 
      result.get(value).add(j); 
     } 
    } 
    return result; 
} 

Ausgang:

case 1 
3 : [2, 1, 0, 1, 2] 
case 2 
3 : [2, 1, 0, 1, 2] 
5 : [1, 0, 1, 0, 1] 

Answer 2

zunächst alle Zahlen finden, die derzeit fünf oder mehr Zeiten sind:

int[] counts = new int[10]; 
for (int r = 0 ; r != 3 ; r++) 
    for (int c = 0 ; c != 5 ; c++) 
     counts[input[r][c]]++; 

Jetzt zählt verwenden, um Index-Arrays zu erzeugen (dies ist so ziemlich eine Neuanordnung der kombinierten Schritte (3) und (4) aus dem Algorithmus):

List<List<Integer>> splitResults = new ArrayList<>(); 
for (int num = 0 ; num != 10 ; num++) { 
    if (counts[num] < 5) { 
     continue; 
    } 
    List<Integer> toAdd = new ArrayList<>(); 
    for (int c = 0 ; c != 5 ; c++) { 
     for (int r = 0 ; r != 3 ; r++) { 
      if (input[r][c] == num) { 
       toAdd.add(r); 
       break; 
      } 
     } 
    } 
    splitResults.add(toAdd); 
} 

Demo.

Answer 3

ich denke, es ist schwer loszuwerden diese Schleifen zu bekommen, aber Sie können es für Fall 2 a funktionieren s unten:

// Gather duplicates 
Map<Integer, Integer> amountMap = new HashMap<>(); 
for (int[] row : railSpin) { 
    for (int value : row) { 
     amountMap.put(value, amountMap.containsKey(value) ? amountMap.get(value) + 1 : 1); 
    } 
} 

// Create index list for 5 matches 
HashMap<Integer,List<Integer>> resultsMap = new HashMap<Integer,List<Integer>>(); 
if (amountMap.containsValue(5)) { 
    for(Integer key : amountMap.keySet()) { 
     if (amountMap.get(key) == 5) { 
      resultsMap.put(key, new ArrayList<Integer>()); 
     } 
    } 
} 

// For all 5 matches, collect indices 
List<Integer> indexList; 
for(Integer index : resultsMap.keySet()) 
{ 
    indexList = resultsMap.get(index); 

    for (int row = 0; row < 5; row++) { 
     for (int col = 0; col < railSpin.length; col++) { 
      if (railSpin[col][row] == index) { 
       indexList.add(col); 
      } 
     } 
    } 
} 

// Print 
StringBuilder sb; 
for(Integer index : resultsMap.keySet()) 
{ 
    sb = new StringBuilder(); 

    indexList = resultsMap.get(index); 
    for(Integer i : indexList) { 
     if(sb.length() == 0) { 
      sb.append("["); 
     } else { 
      sb.append(", "); 
     } 
     sb.append(i.intValue()); 
    } 

    sb.append("]"); 
    System.out.println(sb.toString()); 
} 

Answer 4

aktualisieren: entfernt die Option 2, da es fehlerhaft war und fusionierte beide Optionen in einer Lösung.

Auf 2D-Arrays, gibt es immer die Möglichkeit, zumindest eine verschachtelte Iteration zu vermeiden, indem sie auf einen 1D-Array und spezifische die (implizite) Breite der Reihe reduziert:

int[] input = new int[]{1, 2, 3, 4, 8, 6, 3, 2, 3, 5, 3, 9, 7, 1, 3}; 
int gridWidth = 5; 

Sie dann nur noch eine Iteration für alle Werte. Aber Sie müssen auch Funktionen unterstützen den aktuellen Wert des 2D-Index zu erhalten (x, y):

public static int get_y(int index, int gridWidth) { 
    return floor((index/gridWidth)); 
} 

public static int get_x(int index, int gridWidth){ 
    return index % gridWidth; 
} 

Sie können dann für eine Zeit durch alle Ihre Werte gehen und fügen Sie sie in einem Index HashMap und zähle sie auf eine nach oben Zähler Hash-Karte.

HashMap<Integer, int[]> counts = new HashMap<Integer, int[]>(); 
HashMap<Integer, Integer> times = new HashMap<Integer, Integer>(); 

//iterate once through all values 
for (int i = 0; i < input.length; i++) { 

    // get position in input 
    int x = get_x(i, gridWidth); 
    int y = get_y(i, gridWidth); 
    int value = input[i]; 

    // add indices for this number 
    // or create new indices array 
    int[] indices = counts.get(value); 
    if (indices == null) { 
     indices = new int[gridWidth]; 
     for (int j = 0; j< gridWidth; j++) { 
     //initialze indices with -1 as default 
     indices[j] = -1; 
     times.put(value, 0); //count counter 
     } 
    } 

    // assign values 
    // +1 because 0 means not present 
    indices[x] = y; 
    counts.put(value, indices); 

    // counting up 
    int counter = times.get(value); 
    times.put(value, counter +1); 
} 

Verwenden Indizes Arrays mit fester Breite und ersten Einträgen von -1 bis deutlichen, die Positionen aufgetreten ist oder nicht, während die nicht 0 Positionen verwirren. Inhalt der HashMap für die Eingabe ist:

1 count: 2 
[0] 0 
[1] -1 
[2] -1 
[3] 2 
[4] -1 
2 count: 2 
[0] -1 
[1] 0 
[2] 1 
[3] -1 
[4] -1 
3 count: 5 
[0] 2 
[1] 1 
[2] 0 
[3] 1 
[4] 2 
4 count: 1 
[0] -1 
[1] -1 
[2] -1 
[3] 0 
[4] -1 
5 count: 1 
[0] -1 
[1] -1 
[2] -1 
[3] -1 
[4] 1 
6 count: 1 
[0] 1 
[1] -1 
[2] -1 
[3] -1 
[4] -1 
7 count: 1 
[0] -1 
[1] -1 
[2] 2 
[3] -1 
[4] -1 
8 count: 1 
[0] -1 
[1] -1 
[2] -1 
[3] -1 
[4] 0 
9 count: 1 
[0] -1 
[1] 2 
[2] -1 
[3] -1 
[4] -1 

Von hier können Sie die Daten weiter auf alle Ihre Bedürfnisse verarbeiten kann. Beide Ansätze erfordern noch einige zusätzliche Iterationen (Option 1: for-Schleife für neue Indizes, Option 2: zugrundeliegende Berechnung ArrayList hinzufügen Operationen), aber ich hoffe, dass dies Ihre Bedürfnisse befriedigen kann.

Vorteile dieses Ansatzes:

• alle Indizes werden in einer Iteration (Einpassen des "Rades" Verhalten)
• skalierbar in gewissem Maße (Anzahl der Räder etc.) erzeugt
• Aufspaltung Zählen und Vorkommen in getrennte Karten für leichte Anforderungen auf

Answer 5

Hier ist ein kurzen Lösungen:

final Map<Integer, List<Integer>> res = new HashMap<>(); 
final Map<Integer, Long> occursMap = Stream.of(input).flatMapToInt(e -> IntStream.of(e)).boxed() 
     .collect(Collectors.groupingBy(Function.identity(), Collectors.counting())); 

for (int j = 0; j < input[0].length; j++) { 
    for (int i = 0; i < input.length; i++) { 
     if (occursMap.getOrDefault(input[i][j], 0L) == 5) { 
      res.computeIfAbsent(input[i][j], ArrayList::new).add(i); 
     } 
    } 
}