Java ArrayList remove() 意外结果？

Question

这是我的代码

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

这基本上是为了数数。特定条目的出现次数。如果我提供输入

3494702579
3494702579
3494702579

我正在获取

3494702579
2
3494702579
1

但我应该得到

3494702579
3

我做错了什么？

Answer 1

在内部循环中，当您删除一个元素然后递增 j 时，您实际上可能会跳过一个元素。

但总的来说，更好的方法是使用多集的 HashMap 实现。您当前的解决方案是 O(n^2)，而 HashMap 非常接近 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
}