Определите, Совпадают ли все элементы в списке Java

1. Обзор

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

Мы также рассмотрим временную сложность каждого решения, используя нотацию Big O, что даст нам наихудший сценарий.

2. Пример

Предположим, у нас есть следующие 3 списка:

notAllEqualList = Arrays.asList("Jack", "James", "Sam", "James");
emptyList = Arrays.asList();
allEqualList = Arrays.asList("Jack", "Jack", "Jack", "Jack");

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

3. Основные циклы

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

public boolean verifyAllEqualUsingALoop(List list) {
    for (String s : list) {
        if (!s.equals(list.get(0)))
            return false;
    }
    return true;
}

Это хорошо, потому что , хотя временная сложность составляет O(n) , она часто может выйти рано.

4. Хэш-набор

Мы также можем использовать HashSet , так как все его элементы различны. I f мы преобразуем List в HashSet , и результирующий размер меньше или равен 1, тогда мы знаем, что все элементы в списке равны:

public boolean verifyAllEqualUsingHashSet(List list) {
    return new HashSet(list).size() <= 1;
}

Преобразование Списка в хэш-набор стоит O(n) времени, в то время как размер вызова занимает O(1) . Таким образом, у нас все еще есть общая временная сложность O(n) .

5. API коллекций

Другим решением является использование метода frequency(Collection c, Object o) API Collections . Этот метод возвращает количество элементов в Коллекции c , соответствующих Объекту .

Итак, если результат частоты равен размеру списка, мы знаем, что все элементы равны:

public boolean verifyAllEqualUsingFrequency(List list) {
    return list.isEmpty() || Collections.frequency(list, list.get(0)) == list.size();
}

Как и в предыдущих решениях, временная сложность составляет O(n) , так как внутренне, Коллекции.frequency() использует базовую цикличность.

6. Потоки

Потоковый API в Java 8 дает нам еще больше альтернативных способов определения того, равны ли все элементы в списке.

6.1. отчетливые()

Давайте рассмотрим одно конкретное решение, использующее метод distinct () .

Чтобы проверить, все ли элементы в списке равны, мы подсчитываем отдельные элементы его потока:

public boolean verifyAllEqualUsingStream(List list) {
    return list.stream()
      .distinct()
      .count() <= 1;
}

Если количество этого потока меньше или равно 1, то все элементы равны, и мы возвращаем true .

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

6.2. allMatch()

Метод Stream API allMatch() обеспечивает идеальное решение для определения того, все ли элементы этого потока соответствуют предоставленному предикату:

public boolean verifyAllEqualAnotherUsingStream(List list) {
    return list.isEmpty() || list.stream()
      .allMatch(list.get(0)::equals);
}

Как и в предыдущем примере с использованием потоков, этот имеет временную сложность O(n) , которая является временем прохождения всего потока.

7. Сторонние Библиотеки

Если мы застряли на более ранней версии Java и не можем использовать потоковый API, мы можем использовать сторонние библиотеки, такие как Google Guava и Apache Commons .

Здесь у нас есть два решения, которые очень похожи, повторяя список элементов и сопоставляя его с первым элементом. Таким образом, мы можем легко вычислить временную сложность, равную O(n) .

7.1. Зависимости Maven

Чтобы использовать любой из них, мы можем добавить в наш проект либо guava , либо commons-collections4 соответственно:


    com.google.guava
    guava
    23.0


    org.apache.commons
    commons-collections4
    4.1

7.2. Google Guava

В Google Guava статический метод Iterables.all() возвращает true , если все элементы в списке удовлетворяют предикату:

public boolean verifyAllEqualUsingGuava(List list) {
    return Iterables.all(list, new Predicate() {
        public boolean apply(String s) {
            return s.equals(list.get(0));
        }
    });
}

7.3. Apache Commons

Аналогично, библиотека Apache Commons также предоставляет служебный класс IterableUtils с набором статических служебных методов для работы Итерируемые экземпляры.

В частности, статический метод IterableUtils.matches All() возвращает true , если все элементы в списке удовлетворяют предикату:

public boolean verifyAllEqualUsingApacheCommon(List list) {
    return IterableUtils.matchesAll(list, new org.apache.commons.collections4.Predicate() {
        public boolean evaluate(String s) {
            return s.equals(list.get(0));
        }
    });
}

8. Заключение

В этой статье мы изучили различные способы проверки того, равны ли все элементы в List , начиная с простых функций Java, а затем показывая альтернативные способы с использованием Stream API и сторонних библиотек Google Guava и Apache Commons.

Мы также узнали, что каждое из решений дает нам одинаковую временную сложность O(n) . Тем не менее, мы сами выбираем лучший вариант в зависимости от того, как и где он будет использоваться.

И обязательно ознакомьтесь с полным набором образцов на GitHub .