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

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

案例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？我活在堆栈溢出的力量中

我会怎么做：

遍

历整个表一次以创建索引映射
删除任何没有 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]

我认为很难摆脱这些循环，但您可以使其适用于情况 2，如下所示：

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

更新：删除了选项 2，因为它有缺陷，并将两个选项合并到一个解决方案中。

在 2D 数组上，始终可以选择避免至少一次嵌套迭代，方法是将它们减少为 1D 数组并指定行的(隐式)宽度：

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 位置。输入的哈希图内容为：

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 添加操作)，但我希望这可以满足您的需求。

这种方法的优点：

所有索引都在一次迭代中生成(拟合"轮子"行为)
在一定程度上可扩展(车轮数量等)
将计数和发生次数拆分为单独的映射，以便在计数时发出轻量级请求

首先，找到出现五次或更多次的所有数字：

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

演示。

以下是简短的解决方案之一：

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

相关内容

最新更新

热门标签：