在二维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); 
     } 
    } 
}