Получить все пары значений из списка <Integer>

Question

Например, у меня есть объект List<Integer> со следующим:

3, 6, 5, 3, 3, 6

Результатом будет 3 и 6. Как я могу создать функцию, которая проверяет дубликаты, а затем возвращает 1 значениедубликат (не пара, только один в паре)?Одна проблема, которая может возникнуть, если есть четырехкратные значения: 3, 4, 5, 3, 8, 3, 3 Тогда я хотел бы вернуть 3 и 3. Как я могу это сделать?

Answer 1

Я бы прошел список, подсчитав количество экземпляров каждого из них (сохранив их на карте), а затем создал бы новый список с карты:

List<Integer> values = // the list of values you have
Map<Integer,Integer> counts = new HashMap<Integer,Integer>();

for(Integer value : values) {
    if(counts.containsKey(value)) {
        counts.put(value, counts.get(value)+1);
    } else {
        counts.put(value, 1);
    }
}

List<Integer> resultValues = new ArrayList<Integer>();
for(Integer value : counts.keySet()) {
    Integer valueCount = counts.get(value);
    for(int i=0; i<(valueCount/2); i++) { //add one instance for each 2
        resultValues.add(value);
    }
}
return resultValues;

Это позволяет избежать поведения O (nlogn) при первой сортировке значений, вместо этого работает в O (n).

Answer 2

Я думаю, что путь "map" от @RHSeeger достаточно хорош. Здесь я просто предлагаю другой способ, просто для «развлечения», чтобы вы могли взглянуть. Это как бы дает стабильный результат: первые заполненные пары появляются первыми:

List<Integer> values = ....;
List<Integer> result = new ArrayList<Integer>();
Set<Integer> unpairedValues = new HashSet<Integer>();

for (int i : values) {
  if (unpairedValues.contains(i)) {
    result.add(i);
    unpairedValues.remove(i);
  } else {
    unpairedValues.add(i);
  }
}
// result contains what u want

Answer 3

Один из возможных способов в псевдокоде:

sortedList = sort (list)
duplicates = empty list
while (length (list) > 1)
{
    if (list [0] == list [1] )
    {
         duplicates.append (list [0] )
         list.removeAt (0)
    }
    list.removeAt (0);
}

Answer 4

// ArrayList<Integer> list = {3, 6, 5, 3, 3, 6}
Collections.sort(list);

ArrayList<Integer> pairs = new ArrayList<Integer>();
int last = Integer.MIN_VALUE;  // some value that will never appear in the list
for (Integer cur : list) {
    if (last == cur) {
        pairs.add(cur);
        last = Integer.MIN_VALUE;  // some value that will never appear in the list
    } else {
        last = cur;
    }
}
System.out.println(Arrays.toString(pairs.toArray()));

Будет выводить

[3, 6]

** Редактировать **

Немного лучший алгоритм, модифицирует данный список

// ArrayList<Integer> list = {3, 6, 5, 3, 3, 6}
Collections.sort(list);
int index = 1, last;
while (index < list.size()) {
    last = list.remove(index - 1);
    if (list.get(index - 1) == last) {
        index++;
    }
    if (index == list.size()) {
        list.remove(index - 1);
    }
}