Java: Обнаружить дубликаты в ArrayList?
6 ответов
Самый простой: выведите целый набор в Набор (использующий Набор (Набор) конструктор или Set.addAll), затем посмотрите, имеет ли Набор тот же размер как ArrayList.
List<Integer> list = ...;
Set<Integer> set = new HashSet<Integer>(list);
if(set.size() < list.size()){
/* There are duplicates */
}
Обновление: Если я понимаю Ваш вопрос правильно, у Вас есть 2-й массив Блока, как в
Таблица блоков [] [];
и Вы хотите обнаружить, если какая-либо строка их имеет дубликаты?
В этом случае, я мог сделать следующее, предположив, что реализации Блока "равняются" и "хэш-код" правильно:
for (Block[] row : table) {
Set set = new HashSet<Block>();
for (Block cell : row) {
set.add(cell);
}
if (set.size() < 6) { //has duplicate
}
}
я не на 100% уверен в этом для синтаксиса, таким образом, могло бы быть более безопасно записать это, поскольку
for (int i = 0; i < 6; i++) {
Set set = new HashSet<Block>();
for (int j = 0; j < 6; j++)
set.add(table[i][j]);
...
Set.add возвращает булев false, если добавляемый объект уже находится в наборе, таким образом, Вы могли выровнять короткое замыкание, и кипа на любом добавляют, что возвращается false, если все, что Вы хотите знать, - существуют ли какие-либо дубликаты.
Если Ваши элементы так или иначе Сопоставимы (то, что порядок имеет любое реальное значение, равнодушно - это просто должно согласовываться с Вашим определением равенства), самое быстрое дублирующееся решение для удаления собирается отсортировать список (0 (n журнал (n))) затем, чтобы сделать, единственная передача и искать повторилась элементы (то есть, равные элементы, которые следуют друг за другом) (это - O (n)).
полная сложность будет O (n журнал (n)), который является примерно тем же как, что Вы получили бы с Набором (n времена, долгие (n)), но с намного меньшей константой. Это вызвано тем, что константа в sort/dedup следует из стоимости сравнения элементов, тогда как стоимость от набора, скорее всего, будет следовать из вычисления хеша плюс одно (возможно несколько) сравнения хеша. Если Вы используете основанную на хеше реализацию Набора, то есть, потому что базирующееся Дерево собирается дать Вам O (n logВІ (n)), который еще хуже.
Насколько я понимаю, однако, Вам не нужно к , удаляют дубликаты, но просто тестируют на их существование. Таким образом, Вы должны ручной код сортировка слиянием или алгоритм пирамидальной сортировки на Вашем массиве, который просто выходит из возвращающего true (т.е. "существует дубликат"), если Ваш компаратор возвращается 0 и иначе завершает вид, и пересеките тестирование сортированного массива на повторения. В сортировке слиянием или пирамидальной сортировке, действительно, когда вид завершается, Вы сравните каждую дублирующуюся пару, если оба элемента уже не были в их конечных положениях (который маловероятен). Таким образом настроенный алгоритм сортировки должен привести к огромному повышению производительности (я должен был бы доказать, что, но я предполагаю, настроенный алгоритм должен быть в O (журнал (n)) на однородно случайных данных)
Если Вы надеетесь стараться не иметь дубликаты вообще, то необходимо просто отключить средний процесс обнаружения дубликатов и использовать Набор .
Просто помещенный: 1) удостоверьтесь, что все объекты сопоставимы, 2) сортируют массив, 2) выполняют итерации по массиву и находят дубликаты
Улучшенный код, с помощью возвращаемого значения Set#add вместо того, чтобы сравнить размер списка и набора.
public static <T> boolean hasDuplicate(Iterable<T> all) {
Set<T> set = new HashSet<T>();
// Set#add returns false if the set does not change, which
// indicates that a duplicate element has been added.
for (T each: all) if (!set.add(each)) return true;
return false;
}
Улучшенный код для возврата повторяющихся элементов
- Может найти дубликаты в коллекции
- вернуть набор дубликатов
- Уникальные элементы могут быть получены из набора
public static <T> List getDuplicate(Collection<T> list) {
final List<T> duplicatedObjects = new ArrayList<T>();
Set<T> set = new HashSet<T>() {
@Override
public boolean add(T e) {
if (contains(e)) {
duplicatedObjects.add(e);
}
return super.add(e);
}
};
for (T t : list) {
set.add(t);
}
return duplicatedObjects;
}
public static <T> boolean hasDuplicate(Collection<T> list) {
if (getDuplicate(list).isEmpty())
return false;
return true;
}