Вопрос по java – Простой способ найти, если два разных списка содержат одинаковые элементы?

209

Как проще всего найти, если два списка содержат одинаковые элементы в стандартных библиотеках Java?

Не должно иметь значения, являются ли два списка одним и тем же экземпляром или нет, и не должно иметь значения, отличаются ли параметры типа списков.

например

List list1
List<String> list2; 
// ... construct etc

list1.add("A");
list2.add("A"); 
// the function, given these two lists, should return true

Там, наверное, что-то смотрит мне в лицо, которое я знаю :-)

РЕДАКТИРОВАТЬ: Чтобы уточнить, я искал точно так же элементы и количество элементов, по порядку.

РЕДАКТИРОВАТЬ: Спасибо за указание на очевидный ответ, который я не мог видеть для поиска :-)

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

Это может никогда не повлиять на вас, но имейте в виду, что постоянные наборы гибернации иногда не соблюдают контракт равных - ищите, смотритеopensource.atlassian.com/projects/hibernate/browse/HHH-3799 Pablojim
Как насчет дубликатов? Michael Myers♦
Элементы должны быть в том же порядке? Michael Myers♦

Ваш Ответ

16   ответов
0

s: http://commons.apache.org/collections/apidocs/org/apache/commons/collections/ListUtils.html

public static boolean isEqualList(java.util.Collection list1,
                              java.util.Collection list2)
Это также требует, чтобы элементы списка были в том же порядке.
Конечно, вы можете сделать это при условии, что типы хранятся в списке или сортируются (или у вас настроен компаратор). Однако алгоритм реализации Apache ничем не отличается от обычного list1.equals (list2), за исключением того, что он статический. Я понимаю, где я неправильно понял вопрос, и на самом деле он спрашивал, как сравнить элементы списка в том же порядке. Виноват!
вы можете отсортировать список перед сравнением
@DavidZhao: ссылка мертва.
298

list1.equals(list2)

От Javadoc:

Compares the specified object with this list for equality. Returns true if and only if the specified object is also a list, both lists have the same size, and all corresponding pairs of elements in the two lists are equal. (Two elements e1 and e2 are equal if (e1==null ? e2==null : e1.equals(e2)).) In other words, two lists are defined to be equal if they contain the same elements in the same order. This definition ensures that the equals method works properly across different implementations of the List interface.

Если вы хотите проверять независимо от порядка, вы можете скопировать все элементы в Sets и использовать equals в результирующих наборах:

public static <T> boolean listEqualsIgnoreOrder(List<T> list1, List<T> list2) {
    return new HashSet<>(list1).equals(new HashSet<>(list2));
}

Ограничением этого подхода является то, что он не только игнорирует порядок, но и частоту повторяющихся элементов. Например, еслиlist1 был ["A", "B", "A"] иlist2 был ["A", "B", "B"]Set подход будет считать их равными.

Если вам нужно быть нечувствительным к порядку, но чувствительным к частоте дублирования, вы можете:

sort both lists (or copies) before comparing them, as done in this answer to another question or copy all elements to a Multiset
@amischiefr: ты предлагаешь O (n ^ 2) - лучшее, что ты можешь сделать?
Я не знаю о деталях реализации содержит всех, но кажется, что это может быть плохо. Если содержащийся все вызовы содержит () снова и снова, у вас будет O (n ^ 2) alg. Наборы в целом должны быть O (nlogn)
Не можете ли вы использовать containsAll, если хотите выполнять проверку независимо от заказа?
На самом деле, если наборы просто будут O (nlogn), другой подход - вызвать Collections.sort () в списке, а затем использовать equals. Однако, если вы хотите сохранить порядок, вам нужно будет скопировать список, и это может оказаться дорогостоящим и отдать предпочтение установленному решению ... поэтому вам следует подумать о своей ситуации :-).
@Dennis Проверка размера действительно работает, только если вы знаете, что каждый список содержит только отдельные элементы. Например, учитываяa = [x, y, x] а такжеb = [x, y, z] тогда размеры равны иb.containsAll(a) вернет истину, ноb содержит элемент не вa.
5

но хотел добавить эту нулевую безопасную проверку:

Objects.equals(list1, list2)
6

что это старая ветка, но ни один из других ответов полностью не решил мой вариант использования (я думаю, что Guava Multiset мог бы сделать то же самое, но здесь нет примера). Пожалуйста, извините за мое форматирование. Я все еще новичок в размещении на стеке обмена. Дополнительно сообщите мне, если есть какие-либо ошибки

Допустим, у вас естьList<T> иList<T> б, и вы хотите проверить, равны ли они следующим условиям:

1) O (n) ожидаемое время работы
2) Равенство определяется как: Для всех элементов в a или b число раз, когда элемент встречается в a, равно числу раз, которое элемент встречается в b. Равенство элементов определяется как T.equals ()

private boolean listsAreEquivelent(List<? extends Object> a, List<? extends Object> b) {
    if(a==null) {
        if(b==null) {
            //Here 2 null lists are equivelent. You may want to change this.
            return true;
        } else {
            return false;
        }
    }
    if(b==null) {
        return false;
    }
    Map<Object, Integer> tempMap = new HashMap<>();
    for(Object element : a) {
        Integer currentCount = tempMap.get(element);
        if(currentCount == null) {
            tempMap.put(element, 1);
        } else {
            tempMap.put(element, currentCount+1);
        }
    }
    for(Object element : b) {
        Integer currentCount = tempMap.get(element);
        if(currentCount == null) {
            return false;
        } else {
            tempMap.put(element, currentCount-1);
        }
    }
    for(Integer count : tempMap.values()) {
        if(count != 0) {
            return false;
        }
    }
    return true;
}

Время выполнения - O (n), потому что мы делаем O (2 * n) вставок в хэш-карту и O (3 * n) выбирает хэш-карту. Я не полностью протестировал этот код, так что будьте осторожны :)

//Returns true:
listsAreEquivelent(Arrays.asList("A","A","B"),Arrays.asList("B","A","A"));
listsAreEquivelent(null,null);
//Returns false:
listsAreEquivelent(Arrays.asList("A","A","B"),Arrays.asList("B","A","B"));
listsAreEquivelent(Arrays.asList("A","A","B"),Arrays.asList("A","B"));
listsAreEquivelent(Arrays.asList("A","A","B"),null);
2

когда два списка имеют одинаковые элементы, но разный порядок:

public boolean isDifferentLists(List<Integer> listOne, List<Integer> listTwo) {
    if(isNullLists(listOne, listTwo)) {
        return false;
    }

    if (hasDifferentSize(listOne, listTwo)) {
        return true;
    }

    List<Integer> listOneCopy = Lists.newArrayList(listOne);
    List<Integer> listTwoCopy = Lists.newArrayList(listTwo);
    listOneCopy.removeAll(listTwoCopy);

    return CollectionUtils.isNotEmpty(listOneCopy);
}

private boolean isNullLists(List<Integer> listOne, List<Integer> listTwo) {
    return listOne == null && listTwo == null;
}

private boolean hasDifferentSize(List<Integer> listOne, List<Integer> listTwo) {
    return (listOne == null && listTwo != null) || (listOne != null && listTwo == null) || (listOne.size() != listTwo.size());
}
Вы также можете отметить, почему вы использовалиremoveAll() вместоcontainsAll() (Насколько я понимаю, что если listTwo содержит дубликаты, которые содержатся только один раз в listOne, метод containsAll () будет некорректно сообщать списки как равные).
Я думаю, вам не нужно копировать список.
4

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

public boolean arraysMatch(List<String> elements1, List<String> elements2) {
    // Optional quick test since size must match
    if (elements1.size() != elements2.size()) {
        return false;
    }
    List<String> work = newArrayList(elements2);
    for (String element : elements1) {
        if (!work.remove(element)) {
            return false;
        }
    }
    return work.isEmpty();
}
work.remove (element) - это O (n), поэтому это решение - O (n ^ 2)
Или O (n1 * n2), который является одним и тем же
Я также использовал ту же стратегию, потому что она обрабатывает все сценарии и размер коллекции не так велик, тогда O (n ^ 2) не имеет значения
-2

какой конкретный класс List вы используете. У абстрактного класса AbstractCollection есть метод containsAll (Collection), который принимает другую коллекцию (List - это коллекция) и:

Returns true if this collection contains all of the elements in the specified collection.

Таким образом, если ArrayList передается внутрь, вы можете вызвать этот метод, чтобы увидеть, точно ли они совпадают.

       List foo = new ArrayList();
    List bar = new ArrayList();
    String str = "foobar";

    foo.add(str);
    bar.add(str);

    foo.containsAll(bar);

Причина для метода containsAll () заключается в том, что он перебирает первый список в поисках совпадения во втором списке. Поэтому, если они вышли из строя, функция equals () не поднимет их.

РЕДАКТИРОВАТЬ: Я просто хочу прокомментировать здесь амортизированное время выполнения различных предлагаемых опций. Важно ли время бега? Конечно. Это единственное, что вы должны рассмотреть? Нет.

Стоимость копирования КАЖДОГО отдельного элемента из ваших списков в другие списки требует времени, а также занимает значительную часть памяти (фактически удваивая объем используемой памяти).

Поэтому, если память в вашей JVM не представляет проблемы (как это обычно и должно быть), вам все равно нужно учитывать время, необходимое для копирования каждого элемента из двух списков в два TreeSets. Помните, что он сортирует каждый элемент по мере его поступления.

Мой последний совет? Вам необходимо учитывать ваш набор данных и количество элементов в вашем наборе данных, а также размер каждого объекта в вашем наборе данных, прежде чем вы сможете принять здесь правильное решение. Поиграйте с ними, создайте один из них и посмотрите, какой из них работает быстрее. Это хорошее упражнение.

Это не работает: {1,2,2} .containsAll ({1,1,2}) и наоборот, и оба списка имеют одинаковый размер.
Нет, он просматривает каждый элемент в foo и видит, содержит ли bar этот элемент. Затем он обеспечивает одинаковую длину двух списков. Если для каждого элемента foo в элементе bar есть такой элемент, что foo.element == bar.element и foo.length == bar.length, то они содержат одинаковые элементы.
мы знаем, есть ли гарантия эффективности? или это обычно O (n ^ 2)?
Как и любой другой массив, который выполняет поиск подходящего элемента, наихудшее время выполнения будет O (n ^ 2). В этом случае, похоже, что реализация действительно перебирает один элемент за раз, ища совпадение. Я не буду спекулировать на амортизированном времени выполнения, но да, наихудший случай - O (n ^ 2).
Не должно ли это быть foo.containsAll (bar) & amp; & amp; bar.containsAll (Foo); ?
1

если вы также хотите сделать его нуль-безопасным:

private static <T> boolean listEqualsIgnoreOrder(List<T> list1, List<T> list2) {
    if (list1 == null)
        return list2==null;
    if (list2 == null)
        return list1 == null;
    return new HashSet<>(list1).equals(new HashSet<>(list2));
}
2

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

Если нет, вы можете ухудшиться доIterable или жеCollection что дает вам некоторую гибкость при передаче структур данных, отсортированных по времени вставки, а не во время, когда вы хотите проверить.

Если порядок не имеет значения (и у вас нет повторяющихся элементов), рассмотрите возможность использованияSet.

Если порядок имеет значение, но определяется временем вставки (а у вас нет дубликатов), рассмотритеLinkedHashSet который похож на TreeSet, но упорядочен по времени вставки (дубликаты не учитываются). Это также дает вамO(1) амортизированный доступO(log n).

13

ections, вы можете использоватьCollectionUtils.isEqualCollection который & quot; возвращает истину, если данные Коллекции содержат одинаковые элементы с одинаковым количеством элементов. & quot;

Очень хорошая реализация на основе hashmap. Время выполнения должно быть O (n), и если имеется много повторяющихся элементов, он использует минимальное количество памяти для отслеживания (в основном отслеживает частоту (количество элементов) элементов, используя карту для каждой коллекции). Недостатком является дополнительное использование памяти O (n).
1

public static '<'T'>' boolean isListDifferent(List'<'T'>' previousList,
        List'<'T'>' newList) {

    int sizePrevoisList = -1;
    int sizeNewList = -1;

    if (previousList != null && !previousList.isEmpty()) {
        sizePrevoisList = previousList.size();
    }
    if (newList != null && !newList.isEmpty()) {
        sizeNewList = newList.size();
    }

    if ((sizePrevoisList == -1) && (sizeNewList == -1)) {
        return false;
    }

    if (sizeNewList != sizePrevoisList) {
        return true;
    }

    List n_prevois = new ArrayList(previousList);
    List n_new = new ArrayList(newList);

    try {
        Collections.sort(n_prevois);
        Collections.sort(n_new);
    } catch (ClassCastException exp) {
        return true;
    }

    for (int i = 0; i < sizeNewList; i++) {
        Object obj_prevois = n_prevois.get(i);
        Object obj_new = n_new.get(i);
        if (obj_new.equals(obj_prevois)) {
            // Object are same
        } else {
            return true;
        }
    }

    return false;
}
0

чтобы оба списка не были нулевыми. Если их размеры разные, то эти списки не равны. Построить карты, состоящие из списков & apos; элементы в качестве ключей и их повторы в качестве значений и сравнить карты.

Предположения, если оба списка равны нулю, я считаю их равными.

private boolean compareLists(List<?> l1, List<?> l2) {
    if (l1 == null && l2 == null) {
        return true;
    } else if (l1 == null || l2 == null) {
        return false;
    }

    if (l1.size() != l2.size()) {
        return false;
    }

    Map<?, Integer> m1 = toMap(l1);
    Map<?, Integer> m2 = toMap(l2);

    return m1.equals(m2);
}

private Map<Object, Integer> toMap(List<?> list) {
    //Effective size, not to resize in the future.
    int mapSize = (int) (list.size() / 0.75 + 1);
    Map<Object, Integer> map = new HashMap<>(mapSize);

    for (Object o : list) {
        Integer count = map.get(o);
        if (count == null) {
            map.put(o, 1);
        } else {
            map.put(o, ++count);
        }
    }

    System.out.println(map);
    return map;
}

Пожалуйста, обратите внимание, метод equals должен быть правильно определен для этих объектов. https://stackoverflow.com/a/24814634/4587961

@CodeConfident, большое спасибо! Я обновил ответ. Я буду использовать Мао!
Вы предположили, что элемент не может присутствовать разное количество раз в каждом списке, например[x, x, y] против[x, y, y] вернул бы true с вашей реализацией.
78

думаю, это оправдывает свой ответ.

Как все говорят здесь, использование equals () зависит от порядка. Если вы не заботитесь о заказе, у вас есть 3 варианта.

Option 1

использованиеcontainsAll(), Этот вариант, на мой взгляд, не идеален, потому что он предлагает производительность в худшем случае, O (n ^ 2).

Option 2

Есть два варианта этого:

2a) Если вы не заботитесь о сохранении порядка ваших списков ... используйтеCollections.sort() в обоих списках. Затем используйтеequals(), Это O (nlogn), потому что вы делаете два вида, а затем сравниваете O (n).

2b) Если вам нужно поддерживать списки & apos; Порядок, вы можете сначала скопировать оба списка. Тогда вы можете использовать решение2a в обоих скопированных списках. Однако это может быть непривлекательно, если копирование очень дорого.

Это ведет к:

Option 3

Если ваши требования такие же, как часть2b, но копирование слишком дорого. Вы можете использовать TreeSet, чтобы выполнить сортировку за вас. Дамп каждого списка в свой собственный TreeSet. Он будет отсортирован в наборе, а исходные списки останутся нетронутыми. Затем выполнитеequals() сравнение по обоимTreeSets.TreeSetss может быть построено за время O (nlogn), аequals() является O (n).

Сделайте ваш выбор :-).

EDIT: Я почти забыл ту же оговорку, чтоЛоуренс Гонсалвес указывает на то. Реализация TreeSet устранит дубликаты. Если вы заботитесь о дубликатах, вам понадобится сортированный мультимножество.

Более конкретно, если наличие дубликатов указывает на неравенство, размер списков должен быть одинаковым, прежде чем любая проверка на равенство сможет успешно завершиться.
Если вы заботитесь о дубликатах, вы всегда можете проверить, что размер коллекций равен перед любыми другими тестами.
ContainsAll Я думаю, что дать неправильный ответ, вам нужно будет содержать все в обоих направлениях.a.containsAll(b) && b.containsAll(a)
@laz: проверка размера не сработает, если в двух списках дублируются разные элементы. Например: [A, A, B] и [A, B, B] имеют одинаковый размер.
@Laurence: я согласен, что сообщение laz немного сбивает с толку (я прочитал его несколько раз, прежде чем понял). Насколько я понимаю, он просто пытается предоставить «ярлык» для особого случая, когда выполняются 2 условия: (1) дубликаты имеют значение, и (2) размеры списка различны. В вашем примере, я думаю, Лаз все еще говорит, что необходимо выполнить все те же проверки, которые мы обсуждали. (По крайней мере, так я это прочитал). Если дубликаты НЕ имеют значения, то вы не можете использовать размер в качестве особого случая проверки. Но когда оба условия выполняются, вы можете просто сказать «if (list1.size ()! = List2.size ()) return false ;.
1
list1.equals(list2);

этот класс должен переопределитьequals функция.

 class MyClass
  {
  int field=0;
  @0verride
  public boolean equals(Object other)
        {
        if(this==other) return true;
        if(other==null || !(other instanceof MyClass)) return false;
        return this.field== MyClass.class.cast(other).field;
        }
  }

Примечание: если вы хотите проверить равно на java.util.Set, а неjava.util.Listто ваш объект должен переопределитьhashCode  функция.

следует строка: вернуть this.field == MyClass.class.cast (other); быть возвращенным this.field == MyClass.class.cast (other) .field;
1

списки упорядочены, поэтому чтобы быть равными, два списка должны иметь одинаковые элементы в одинаковом порядке.

return list1.equals(list2);
Я имею в виду, что список, содержащий {& quot; A & quot ;, & quot; B & quot;} и список, содержащий {& quot; B & quot ;, & quot; A & quot;}, будет неравным с этим способом. Это вполне может быть то, что задумано, но я хотел убедиться, что никто не пропустил это.
Я думаю, что daveb подразумевает, что списки упорядочены, это то, что List.equals учитывает порядок элементов для определения равенства. Смотрите Javadoc.
Списки не упорядочены, если вы не сортируете их.
@mmyers: предметыin списки не упорядочены, если вы не сортируете их. Сами списки имеют неявное упорядочение элементов (по индексу), которое не изменится, пока вы не измените элементы в списке. (по сравнению с наборами или коллекциями, где нет гарантии последовательного упорядочения, если вы повторяете их дважды)
Вздох @ Myself. Такой очевидный ответ. Вы знаете, что это был слишком длинный день, когда вы больше не можете даже Ctrl + F веб-страницы. :) Grundlefleck

Похожие вопросы