Как найти кратные числа того же целого числа в arraylist?
Моя проблема следующие. У меня есть arraylist целых чисел. arraylist содержит 5 ints, например, [5,5,3,3,9] или возможно [2,2,2,2,7]. Многие arraylists имеют дублирующиеся значения, и я не уверен, как рассчитать, сколько из каждого из значений существует.
Проблема состоит в том, как найти дублирующиеся значения в arraylist и рассчитать, сколько из того конкретного дубликата существует. В первом примере [5,5,3,3,9] существуют 2 5's и 2 3's. Второй пример [2,2,2,2,7] был бы только 4 2's. Получающаяся информация, которую я хочу найти, - то, если существуют какие-либо дубликаты сколько из них существует и какое определенное целое число было дублировано.
Я не слишком уверен, как сделать это в Java.
Любая справка очень ценилась бы.Спасибо.
6 ответов
Для меня наиболее простым ответом было бы использование метода 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.");
}
Если хотите, вы можете сопоставить каждое целое число с его количеством вхождений:
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (Integer i : noDupes) {
map.put(i, Collections.frequency(intList, i));
}
Вы можете просмотреть список и поместите их на Карту с подсчетом. Тогда легко определить, какой из них дублируется.
Используйте коллекцию Hashmap в дополнение к списку массивов, где
- ключ Hashmap - это уникальное значение массива int, а
- значение Hashmap для ключа - это счетчик каждого обнаруженного значения.
Обходите свой список массивов, собирая эти значения в хэш-карту, добавляя новый элемент, когда предыдущий ключ не существует, и увеличивая на 1 значения ключей, которые уже существуют. Затем выполните итерацию по Hashmap и распечатайте все ключи, значение которых> 1.
Вот конкретная реализация с тестом того, что я описал в комментариях к ответу @Tom:
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;
}
}
Для более четкой абстракции того, что вы делаете, вы можете использовать структуру данных Multiset из guava / google-collections . Вы даже можете обнаружить, что предпочитаете использовать его, чем List , в зависимости от того, что вы с ним делаете (если вам не требуется детерминированное упорядочение списка). Вы бы использовали его так:
Multiset<Integer> multiset = HashMultiset.create(list);
int count = multiset.count(3); // gets the number of 3s that were in the list
С точки зрения того, что вышеупомянутое делает под обложками, это почти точно эквивалентно предложению построить Map на основе вашего списка.
На ум приходят два алгоритма.
Сортировать ( Collections.sort ). Затем выполните итерацию, легко находя обманщиков.
Итерировать, сохраняя счетчик в Map (или Map для изменяемого счетчика). Это немного некрасиво.
В любом случае, его кодирование должно быть поучительным упражнением. Предлагаю сделать и то, и другое, и сравнить.