CODEWITHSUNDEEP
javaalgorithm
kang
kang

Reputation: 707

Find gaps between repeated numbers in an array

I have an ArrayList with a list of numbers. Each number is always between 0 - 9. So the ArrayList contains numbers something as follows:

1 2 7 4 9 1 8 8 3 2 9 0 1 3 ....

I want to count the gaps before the number repeats again. For example the number 1 has a gap of 4 before repeating again. And then it goes on to have another gap of 6. I am looking to find out gaps up to 30. The list is long. I am looking to store and produce the following: 

Number 0 gap 1 : none
Number 0 gap 2: 5 times
Number 0 gap 3: 7 times
.....
Number 0 gap 30: none
Number 1 gap 1: 5 times
Number 1 gap 2: 3 times
......
Number 9 gap 30: 2 times

I really can't get my head around to how I could do this. I tried the following but it is clearly going nowhere. Looking for some direction and help please.

//arr is the ArrayList

int gapCount = 0;
int[] gaps = new int[10];

for (int i = 0; i < arr.size(); i++) {
     for (int j = 0; j < arr.size(); j++) {
        if(arr.get(i) == arr.get(j)){

        }
        gapCount++;
     }
}

Upvotes: 2

Views: 1976

Answers (3)

Loris Securo
Loris Securo

Reputation: 7638

You could use a two dimensional array to keep the gaps:

int[][] gaps = new int[10][30];

You would use it to keep the occurrences of the gaps like this:

gaps[0][0] keep the gaps of Number 0 gap 1

gaps[0][1] keep the gaps of Number 0 gap 2

...

gaps[1][0] keep the gaps of Number 1 gap 1

and so on.

The code would look like this:

int[][] gaps = new int[10][30];

for (int i = 0; i < (arr.size() - 1); i++) {

    int gapCount = 0;  // reset the gap count for the actual number

    for (int j = i + 1; j < arr.size(); j++) {

        if (arr.get(i) == arr.get(j)) {

            // we only track gaps greater than zero
            if(gapCount > 0) {  
                gaps[arr.get(i)][gapCount - 1]++; // increment the gap occurrence
            }

            break; // go to the next number in the list
        }

        gapCount++;

        // we don't want to track gaps greater than 30
        if(gapCount > 30) {
            break;
        }
    }
}

Upvotes: 1

user152468
user152468

Reputation: 3242

One more answer: 

public class GapFinder {

  public HashMap<Integer, HashMap<Integer, Integer>> findGaps(List<Integer> input) {
    HashMap<Integer, Integer> lastSeen = new HashMap<Integer, Integer>();
    HashMap<Integer, HashMap<Integer, Integer>> result = new HashMap<Integer, HashMap<Integer, Integer>>();
    for (int position = 0; position < 10; position++) {
        result.put(position, new HashMap<Integer, Integer>());
    }
    for (int position = 0; position < input.size(); position++) {
        int number = input.get(position);
        if (lastSeen.get(number) != null) {
            int diff = position - lastSeen.get(number);
            if (result.get(number).get(diff) == null) {
                result.get(number).put(diff, 1);
            } else {
                int previous = result.get(number).get(diff);
                int incremented = previous + 1;
                result.get(number).put(diff, incremented);
            }
        }
        lastSeen.put(number, position);
    }
    return result;
  }
}

Upvotes: 0

Damien Prot
Damien Prot

Reputation: 593

Something like that could work, it is really the basics of Java : 

    List<List<Integer>> gaps = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        gaps.add(new ArrayList<Integer>());
    }

    int lastPosition[] = new int[10];
    Arrays.fill(lastPosition, -1);

    for (int curIndex = 0; curIndex < arr.size(); curIndex++) {
        Integer curValue = arr.get(curIndex);
        if (lastPosition[curValue] != -1) {
            gaps.get(curValue).add(curIndex - lastPosition[curValue]);
        }
        lastPosition[curValue] = curIndex;
    }

    for (int i = 0; i < 10; i++) {
        if (gaps.get(i).isEmpty())
            System.out.print("Number " + i + ": none\n");
        else
            for (int index = 0; index < gaps.get(i).size(); index++)
                System.out.print("Number " + i + " gap " + index + " : " + gaps.get(i).get(index) + "\n");

    }

You should adapt it to your 30-limit of course, but that is easy.

Upvotes: 0

Related Questions