Вложенная петля для подсчета дубликатов в ArrayList работает неправильно

Question

У меня есть следующий метод, который берет ArrayList строк, где каждая строка является координатой в виде «(x, y)». Предполагается, что метод подсчитывает количество раз, когда какая-либо из этих координат появляется более одного раза в списке.

Вот мой код:

public static int duplicateHouses(ArrayList<String> houses){ 
     int duplicateCount = 0; 

     for(int i = 0; i < houses.size(); i++){ 
      for(int j = i + 1; j < houses.size(); j++){ 
       if((houses.get(i)).equals(houses.get(j))){ 
        duplicateCount++; 
       } 
      } 
     } 

     return duplicateCount; 
    } 

Он заканчивает возвращающее число, которое намного больше, чем количество строк в моем списке. Где я иду не так?

Answer 1

Если у вас есть по крайней мере 4 дубликаты в List, первый цикл будет найти 3, то второй цикл будет найти 2, третий цикл будет найти 1, что дает результат 6. В принципе, каждый цикл снова находит одни и те же дубликаты.

Например ...

public static void main(String[] args) { 
    ArrayList<String> houses = new ArrayList<>(25); 
    houses.add("(1x1)"); 
    houses.add("(1x2)"); 
    houses.add("(1x1)"); 
    houses.add("(1x3)"); 
    houses.add("(1x1)"); 
    houses.add("(1x4)"); 
    houses.add("(1x1)"); 
    houses.add("(1x5)"); 

    System.out.println(houses.size()); 
    System.out.println(duplicateHouses2(houses)); 
} 

public static int duplicateHouses(ArrayList<String> houses) { 
    int duplicateCount = 0; 

    for (int i = 0; i < houses.size(); i++) { 
     System.out.println("---"); 
     for (int j = i + 1; j < houses.size(); j++) { 
      if ((houses.get(i)).equals(houses.get(j))) { 
       System.out.println(i + ": " + houses.get(i) + " == " + j + ": " + houses.get(j)); 
       duplicateCount++; 
      } 
     } 
    } 

    return duplicateCount; 
} 

Какие выходы ...

--- 
0: (1x1) == 2: (1x1) 
0: (1x1) == 4: (1x1) 
0: (1x1) == 6: (1x1) 
--- 
--- 
2: (1x1) == 4: (1x1) 
2: (1x1) == 6: (1x1) 
--- 
--- 
4: (1x1) == 6: (1x1) 
--- 
--- 
--- 

Теперь вы можете, создать копию List и удалить каждый дубликат, как вы найдете его, или вы могли бы используйте второй номер List для хранения повторяющихся значений.

Я попытался вычисления разности между Set значений и исходного List, но это возвращается значение, которое было 1 меньше ожидаемого результата (в приведенном выше примере это возвращенного 3 вместо 4)

Вместо этого, Я использовал Stream#filter оригинала и Set для создания дубликата счета

Например ...

public static int duplicateHouses(ArrayList<String> houses) { 
    // Make sure we only have 1 of each possible value 
    Set<String> copy = new HashSet<>(houses); 
    int duplicateCount = 0; 
    // For each value, we want to filter the original 
    // list so that only matching values remain... 
    for (String value : copy) { 
     Stream<String> filter = houses.stream().filter((String t) -> t.equals(value)); 
     // If there is more then one, then there are duplicates... 
     long count = filter.count(); 
     if (count > 1) { 
      duplicateCount += count; 
     } 
    } 
    return duplicateCount; 
} 

что, учитывая первый экс ample, возвращает 3

Answer 2

Это потому, что вы зацикливаете 2 раза, поэтому каждая запись сообщит вам, что я дублирую 2 раза.

Допустим, вы же координату/дом на 2, 5 и 10. В настоящее время в соответствии с существующей логики, когда ваш первый цикл выполняется для i=2, то это даст вам YES для 5 и 10 и ваш duplicateCount будет 2, который будет правильным. Но когда ваш первый цикл будет работать для i=5, он снова даст вам ДА за 10. И вот где вы получите проблему.

Итак, что вы можете сделать, это инкремент duplicateCount только один раз для вашего первого цикла FOR, так что, хотя есть еще 100 записей, тогда он не будет увеличивать duplicateCount и будет увеличиваться только при последовательном запуске первого цикла FOR, который будет предотвращать дублирование приращения duplicateCount.

Попробуйте ниже:

public static int duplicateHouses(ArrayList<String> houses){ 
    int duplicateCount = 0; 
    ArrayList<String> dupHouses = new ArrayList<String>; 

    for(int i = 0; i < houses.size(); i++){ 
     for(int j = i + 1; j < houses.size(); j++){ 
      if((houses.get(i)).equals(houses.get(j))){ 
       if(!dupHouses.contains(houses.get(j))){ 
        duplicateCount++; 
        dupHouses.add(houses.get(j)); 
       } 
      } 
     } 
     dupHouses = new ArrayList<String>; //Reset for next iteration ... 
    } 
    return duplicateCount; 
}