Структура данных: уникальность в списках

Question

У меня есть 2 списка, один список l1 содержит n1 элементов, а другой список l2 содержит n2 элементов. Оба списка не имеют одинаковую длину и содержат повторяющиеся элементы. Я хочу создать другой список, который имеет уникальные элементы из l1 и l2. Как я могу сделать это эффективно и какова будет производительность этого решения?

P.S: я хочу решение, которое не использует никаких других структур данных.

Answer 1

Если вы не можете использовать Set, я думаю, что лучшее решение - выполнить сортировку слиянием без дубликатов.Этот вопрос SO может помочь: Как использовать сортировку слиянием для удаления дубликатов?

Answer 2

Решением O (nlogn) было бы отсортировать каждый список, а затем просмотреть оба списка вместе, чтобы найти дубликаты.Вы должны увеличить позицию одного или другого списка (или обоих) в зависимости от того, какой список имеет «наименьшее» значение текущего элемента (или если они одинаковые).Есть разумные издержки, поэтому некоторые алгоритмы O (n ^ 2) на самом деле могут быть быстрее в зависимости от размера / распределения данных.

Answer 3

Если вам нужно использовать только списки, и у вас есть возможность дублировать их как внутри каждого списка, так и между списками, то вам нужно создать новый список l3 (для хранения объединения элементов l1 и l2) и выполнить итерациюкаждый список, вставляя каждый элемент элемента e, если вызов l3.contains (e) возвращает false.

Как уже упоминали другие, использование Set, безусловно, самый простой способ удалить дублирующиеся элементы спискаи из набора можно создать список для возврата вызывающей стороне.

Производительность линейная и основана на количестве элементов в l1 + l2.

Answer 4

Создайте новый набор и добавьте элементы из списков l1 и l2.Финальный набор будет без дубликатов.Но убедитесь, что вы правильно реализовали equals () и hashCode ().

Ниже приведен мой пример (не идеальный) для того же.Разместите его здесь, чтобы проверить мою логику ;-) или посмотреть, есть ли лучшие способы оптимизации этого

Lit unique=...


if(l1.size==l2.size())
{
    //o(n)
    copyToUnique(l1, l2, unique)
}
else if(l1.size>l2.size())
{
    //o(n) + num of extra elements
    copyToUnique(l1, l2, unique)
    unique.addAll(l1.subList(l2.size(),l1.size());
}
else if(l1.size<l2.size())
{
    //o(n) + num of extra elements
    copyToUnique(l2, l1, unique)
    unique.addAll(l2.subList(l1.size(),l2.size());
}

public void copyToUnique(List l1, List l2, List unique)
{
    for(Object element:l1)
    {
        if(!l2.contains(element))
        {
            unique.add(element);
        }
    }
unique.addAll(l2);
}