在二維int數組算法中收集重複值的索引

Question

我正在使用老虎機並面臨收集結果結果的問題。問題是在2D int數組中收集重複值索引的最快方法是什麼？這裏的條件是，以收集值的僅idexes其中發生5倍

CASE 1

輸入（獲取值只的索引）：

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

預期輸出：

[2, 1, 0, 1, 2] 

CASE 2

輸入（獲取的和值僅索引）：

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

預期輸出：

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

我的解決方案（其相當差）

1）收集重複（爲CASE 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）這一個不工作除去非5場比賽

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

3）迭代倒置並收集索引

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）如果需要分割陣列

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

您能否建議一個沒有太多迭代的解決方案，哪個適合CASE 2？我相信在計算器的功率

Answer 1

計數，出現成輕質請求單獨的地圖如何我會做到這一點：

1. 遍歷整個表一次，以創建一個地圖索引
2. 刪除尚未5有效指標

編輯任何條目：我切換到使用ArrayList的工作，因爲它只是一個更好：

代碼：

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

輸出：

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

Answer 2

首先，找到存在的五倍以上所有數字：

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

現在的使用次數生成索引數組（這是相當多的合併步驟的重新排列（ 3）和（4）從你的算法）：

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

我覺得這很難擺脫這些循環的，但你可以把它的情況下2工作S下方所示：

// 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

更新：移除選項2，因爲它是有缺陷的併合並這兩個選項到一個解決方案。

在2D陣列，總有，以避免在至少一個嵌套的迭代的選項，通過將它們減少到一維陣列和行的特定的（隱含的）寬度：

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

您那麼只需要對所有值進行一次迭代。但你也需要支持功能來獲取當前值的2D指數（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; 
} 

然後你可以通過你所有的值一次並將它們添加到索引HashMap和指望他們了上計數器哈希映射。

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

使用具有固定寬度和初始條目-1的索引數組來區分，哪些位置是否發生，而不會混淆0位置。輸入的HashMap的內容是：

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 

從這裏您可以進一步處理所有需求的數據。這兩種方法仍然需要一些額外的迭代（選項1：for循環的新索引，選項2：底層計算ArrayList添加操作），但我希望這可以滿足您的需求。這種方法的

優點：

• 所有索引被在一次迭代（擬合「輪」的行爲）
• 可擴展到一定程度
• 分裂的（輪子的數量等）中產生在計數

Answer 5

這裏是短期的解決方案之一：

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