Java ArrayList remove() unexpected result?

Question

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

But I should get

3494702579
3

What am I doing wrong?

Petar Ivanov · Accepted Answer · 2013-03-23 07:48:02Z

2

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
}

edited Mar 23, 2013 at 7:48

answered Mar 23, 2013 at 7:42

Petar Ivanov

93.4k11 gold badges84 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

NPE · Accepted Answer · 2013-03-23 07:39:35Z

2

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.

answered Mar 23, 2013 at 7:39

NPE

503k114 gold badges970 silver badges1k bronze badges

Collectives™ on Stack Overflow

Java ArrayList remove() unexpected result?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related