Как найти кратные одного и того же целого числа в массиве?

Question

Моя проблема заключается в следующем. У меня есть массив целых чисел. Arraylist содержит 5 дюймов, например [5,5,3,3,9] или, возможно, [2,2,2,2,7]. Многие из массивов имеют повторяющиеся значения, и я не уверен, как подсчитать, сколько существует каждого из значений.

Проблема в том, как найти повторяющиеся значения в массиве и подсчитать, сколько из этого конкретного дубликата существует. В первом примере [5,5,3,3,9] есть 2 5 и 2 3. Второй пример [2,2,2,2,7] будет только 4 2. Полученная информация, которую я хочу найти, состоит в том, есть ли дубликаты, сколько их и какое конкретное число было продублировано.

Я не слишком уверен, как это сделать в Java.

Любая помощь будет высоко ценится. Спасибо.

Answer 1

Для меня самым простым ответом будет использование метода Collections.frequency. Что-то вроде этого:

// Example ArrayList with Integer values
ArrayList<Integer> intList = new ArrayList<Integer>();
intList.add(2);
intList.add(2);
intList.add(2);
intList.add(2);
intList.add(7);

Set<Integer> noDupes = new HashSet<Integer>();
noDupes.addAll(intList); // Remove duplicates

for (Integer i : noDupes) {
    int occurrences = Collections.frequency(intList, i);
    System.out.println(i + " occurs " + occurrences + " times.");
}

Если вы хотите, вы можете сопоставить каждый Integer с его количеством вхождений:

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (Integer i : noDupes) {
    map.put(i, Collections.frequency(intList, i));
}

Answer 2

На ум приходят два алгоритма.

Сортировка (Collections.sort). Затем выполните итерацию, легко найдя парней.

Итерация по счету в Map<Integer,Integer> (или Map<Integer,AtomicInteger> для изменяемого счетчика). Немного безобразно, таким образом.

В любом случае, кодирование должно быть поучительным упражнением. Я предлагаю сделать и сравнение, и сравнение.

Answer 3

Вот конкретная реализация с тестом того, что я описал в комментариях к ответу @ Тома:

package playground.tests;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;

import junit.framework.TestCase;

public class DupeCounterTest extends TestCase {

    public void testCountDupes() throws Exception {
        int[] array = new int[] { 5, 5, 3, 3, 9 };
        assertEquals("{3=2, 5=2}", countDupes(array).toString());
    }

    private Map<Integer, AtomicInteger> countDupes(int[] array) {
        Map<Integer, AtomicInteger> map = new HashMap<Integer, AtomicInteger>();
        // first create an entry in the map for every value in the array
        for (int i : array)
            map.put(i, new AtomicInteger());
        // now count all occurrences
        for (int i : array)
            map.get(i).addAndGet(1);
        // now get rid of those where no duplicate exists
        HashSet<Integer> discards = new HashSet<Integer>();
        for (Integer i : map.keySet())
            if (map.get(i).get() == 1)
                discards.add(i);
        for (Integer i : discards) 
            map.remove(i);
        return map;
    }

}

Answer 4

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

Answer 5

Используйте коллекцию Hashmap в дополнение к списку массивов, где

• ключ Hashmap - это уникальное значение массива int, а
• значение Hashmap для ключа является счетчиком каждого найденного значения.

Пройдите по списку массивов, собирая эти значения в хэш-карту, добавляя новый элемент, когда предыдущий ключ не существует, и увеличивая на 1 значения ключей, которые уже существуют. Затем выполните итерацию по Hashmap и распечатайте все ключи, где значение> 1.

Answer 6

Для более ясной абстракции того, что вы делаете, вы можете использовать структуру данных Multiset из guava / google-collection . Вы даже можете обнаружить, что предпочитаете использовать его, а не List, в зависимости от того, что вы делаете с ним (если вам не нужен детерминированный порядок списка). Вы бы использовали это так:

Multiset<Integer> multiset = HashMultiset.create(list);
int count = multiset.count(3); // gets the number of 3s that were in the list

С точки зрения того, что вышеупомянутые действия делают под прикрытием, это почти в точности эквивалентно предложению построить Map<Integer,AtomicInteger> на основе вашего списка.