Java ArrayList удалить() неожиданный результат?

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 ключей для подсчета и одного прохода по списку ввода.