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
}

Answer 2

在对m1进行迭代时，您正在从中删除元素。这会导致内部循环跳过某些元素。发生这种情况的原因是，在删除第j个元素之后，仍然在增加j

在您的示例中，其中一个3494702579被跳过，并由外循环的第二次迭代拾取

您的方法的整个逻辑可以使用Map个键来重写，只需对输入列表进行一次遍历