java - 在 2D int 数组算法中收集重复值的索引

Question

我在老虎机上工作，遇到了收集结果的问题。问题是在 2D int 数组中收集重复值索引的最快方法是什么？这里的条件是只收集出现5次

的值的索引

案例 1

输入(仅获取3值的索引):

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]

案例 2

输入(仅获取3和5值的索引):

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) 收集重复项(这个不适用于案例 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 的解决方案？我相信 stackoverflow 的力量

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]