Способ удалить коллекцию из связанного списка - PullRequest
Новая
       23

Способ удалить коллекцию из связанного списка

0 голосов
/ 10 октября 2018

Я пытаюсь создать метод для удаления каждого появления значений коллекции "L2" из связанного списка "L1".Мне интересно, как это сделать.В настоящее время я думаю о создании HashSet из значений коллекции "L2" и его удалении, мне просто интересно, есть ли способ сделать этот метод с временным ограничением O (n).

Забылиупоминание как Linkedlist L1, так и Collection L2 не отсортированы.Оба сделаны из целых чисел.

Ответы [ 2 ]

0 голосов
/ 11 октября 2018

Вы можете использовать LinkedList.removeAll на L1, используя HashSet для L2, если это еще не HashSet: 

L1.removeAll(L2 instanceof HashSet ? L2 : new HashSet<>(L2));

На более высоком уровне это повторяет L1 перечисляет и удаляет каждый элемент на месте, если он принадлежит другой коллекции L2.

Внутренне LinkedList.removeAll использует свой Iterator для обхода своих элементов, а затем использует метод contains другой коллекции, чтобы проверить, должен ли элемент быть удален.Если contains возвращает true, он удаляет элемент с помощью метода Iterator.remove.

Теперь использование Iterator.remove для LinkedList является O(1) худшим случаем, поскольку удаляемый элементэто элемент, на который в данный момент указывает итератор.И использование contains над HashSet является средним O(1), поэтому все решение будет либо O(n), если L2 уже равно HashSet, либо O(n+m), если нет.(Здесь n=L1.size() и m=L2.size()).

0 голосов
/ 11 октября 2018

Вызов remove в связанном списке для элемента не является O (1);это находится на).Таким образом, вы правы в том, что вызов remove для каждого элемента L2 даст вам время O (mn).

Чтобы весь процесс удаления O (n + m), выможно отфильтровать значения во временный список и затем перестроить L1, но вам также понадобится набор для элементов L2, чтобы вы могли выполнить эту проверку фильтра за O (1) раз. 

public static LinkedList<Integer> removeAll(LinkedList<Integer> L1, Collection<Integer> L2) {
    LinkedList<Integer> temp = new LinkedList<>();
    HashSet<Integer> L2Set = new HashSet<>(L2); // O(m)

    // first filter elements into temp
    while (L1.size() > 0) { // n loops
        int v = L1.removeFirst(); // O(1)
        if (!L2Set.contains(v)) { // O(1)
            temp.addLast(v);      // O(1)
        }
    }

    // add filtered values back to L1
    while (temp.size() > 0) {     // About n loops
        L1.addLast(temp.removeFirst()); // O(1)
    }

    return L1;
}

Примечаниечто мы используем только addLast и removeFirst, которые являются операциями O (1), что дает нам линейное время выполнения.

Это также сохраняет первоначальное упорядочение элементов в L1.

...