CODEWITHSUNDEEP
java
Ananda
Ananda

Reputation: 1572

Java ArrayList remove() unexpected result?

Here is my code

void reduce() {
    KeyVal reducer1 = new KeyVal();
    for (int i=0; i< m1.size(); i++) {
        reducer1.setKey(m1.get(i).getKey());
        reducer1.setValue(m1.get(i).getValue());

        for (int j=i+1; j < m1.size(); j++) {
              if (m1.get(i).getKey().compareTo(m1.get(j).getKey()) == 0) {
                  m1.remove(j);
                  //System.out.println(i + "-->" + j);
                  reducer1.setValue(reducer1.getValue() + 1);
              }
          }         

        System.out.println(reducer1.getKey());
        System.out.println(reducer1.getValue());
        //r1.add(reducer1);
      }

It's basically for counting no. of occurrences of particular entry. If i am giving input

3494702579
3494702579
3494702579

I am getting 

3494702579
2
3494702579
1

But I should get

3494702579
3

What am I doing wrong?

Upvotes: 0

Views: 65

Answers (2)

Petar Ivanov
Petar Ivanov

Reputation: 93030

In your inner loop, when you remove an element and then increment j you in fact might skip an element.

But in general a better way to do what you want is to use HashMap implementation of multi set for example. Your current solution is O(n^2), while the HashMap one is very close to O(N).

void reduce() {
    HashMap<xxx, Integer> reducer1 = new HashMap<xxx, Integer>();
    for (int i=0; i< m1.size(); i++) {
        xxx key = m1.get(i).getKey();

        int count = 0;
        if ( reducer1.containsKey(key) ) count = reducer1.get(key);

        reducer1.put(key, count+1);  
     }
     //print the values
}

Upvotes: 2

NPE
NPE

Reputation: 500367

You are removing elements from m1 while iterating over it. This causes the inner loop to skip some elements. This happens because, after you've removed the j-th element, you are still incrementing j.

In your example, one of the 3494702579 gets skipped, and is picked up by the second iteration of the outer loop.

The entire logic of your method can be rewritten using a Map of keys to counts, and a single pass over the input list.

Upvotes: 2

Related Questions