Clever Geek Handbook

Collect indices of duplicate values ​​in 2D int array algorithm

I am working on a slot machine and am facing a problem collecting results. The question is, what is the fastest approach to collect indices of duplicate values ​​in a 2D array? The condition here is to only collect the ideals of values ​​that occur 5 times

CASE 1

(get only 3 indices ):

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

expected output:

[2, 1, 0, 1, 2]

CASE 2

(get indices only 3 and 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}
    };

expected output:

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

MY SOLUTION (its pretty bad)

1) collect duplicates ( this one doesn't work for 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) remove not 5 matches

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

3) iterating upside down and collecting indices

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 the array if necessary

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

Can you suggest a solution without so many iterations and that is suitable for CASE 2 ? I believe in the power of stackoverflow

+3


source to share


5 answers


How would I do it:

  • Iterate over the entire ONCE table to create an index map
  • Remove any entry that does not have 5 valid indices

EDIT: I switched to working with ArrayList because it's just better:

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

Output:

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


source


First, find all numbers that appear five or more times:

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

Now, use counts to create indexed arrays (this is pretty much a re-arrangement of combined steps (3) and (4) from your algorithm):



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 version

+1


source


I am having a hard time getting rid of these loops, but you can make it work for case 2 like below:

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


source


Update : Removed option 2 as it was wrong and combined both options into one solution.

In 2D arrays, it is always possible to avoid at least one nested iteration by reducing them to a 1D array and defining the (implicit) string width:

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

You only need one iteration for all values. But you also need supporting functions to get the current 2D index value (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;
}

Then you can look at all your values ​​in one go and add them to the HashMap index and count them in the hash counter map.

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

Use arrays of indices with fixed width and initial values ​​from -1 to different which positions occurred or not, but do not confuse 0 positions. HashMap content for input:

 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

Then you can process the data for all your needs. Both approaches still require some additional iteration (Option 1: for looping for new indexes, Option 2: basic ArrayList computation adds operations), but I hope this can satisfy your needs.

The advantages of this approach:

  • all indexes are generated in one iteration (when setting the "wheel" behavior)
  • scalable to a certain extent (number of wheels, etc.).
  • splitting counting and inputs into separate cards for easy counting queries
+1


source


Here's one of the shortcuts:

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


source






More articles:


All Articles