Два несортированных списка Пересечение возвращено как список

Question

Мой вопрос: возможно ли получить 2 несортированных списка и получить пересечение обоих списков в соответствии с порядком, который был в первом списке «List1».

public static List intersection(List A, List B) {

    List outcome = null;

    try {
        outcome = A.getClass().newInstance();
    } catch (Exception e) {};

    LinkedList<Integer> temp = new LinkedList<>();

    LinkedHashSet<Integer> ALinkedSet = new LinkedHashSet<>(A); 
    LinkedHashSet<Integer> BLinkedSet = new LinkedHashSet<>(B);

    // first filter elements into temp
    while (ALinkedSet.size() > 0) { 
        int v = ALinkedSet.removeFirst(); 
        if (BLinkedSet.contains(v)) { 
            temp.addLast(v);      
        }
    }

    // add filtered values back to L1
    while (temp.size() > 0) {     
        outcome.addLast(temp.removeFirst()); 
    }

    return outcome;
}

Я ищу способ сделать эту работу и, возможно, включить ее в O (n).

Вот простой рисунок.Есть ли лучший способ превратить большой O в линейный?Я почти уверен, что это O (n * n) по крайней мере.

public static List Intersection(List A, List B) {

    List outcome = null;

    try {
        tulos = A.getClass().newInstance();
    } catch (Exception e) {};

    LinkedHashSet<Integer> AHashSet = new LinkedHashSet<>(A); 
    LinkedHashSet<Integer> BHashSet = new LinkedHashSet<>(B);

    for(Integer Aitem : AHashSet){
        for(Integer Bitem : BHashSet){
            if(Aitem==Bitem) {
                outcome.add(Aitem);
            }
        }
    }

    return outcome;
}

Будет ли следующее линейным?

public static List Intersection(List A, List B) {

 List outcome = null;

   try {
        tulos = A.getClass().newInstance();
    } catch (Exception e) {};

 LinkedHashSet<Integer> BHashSet = new LinkedHashSet<>(B);

    for(Object Aitem : A) {
        if(BHashSet.contains(Aitem) && !outcome.contains(Aitem)){
         outcome.add(Aitem);

           }
    }
    return outcome;

}

Answer 1

Обновление: поскольку мы можем использовать только LinkedHashMaps ...

... и списки могут иметь дубликаты:

1. Создать ListEntryкласс, который имеет число и общее количество повторений числа в списке.Таким образом, если 2 встречается дважды, мы создадим new ListEntry(number: 2, count: 2); в LinkedHashMap (LHM);
2. Заполните LHM из ListEntry объектов, используя числа, присутствующие в первом списке;
3. Теперь переберите второй список, просматривая его номера один за другим:
   1. Если номер второго списка не найден, переходите к следующему номеру;
   2. Для каждого найденного номера приведитеего запись в LHM на передний план, сохранить его «видимый» счет в хэш-карте (numberSeen) и обновить другой счетчик (intersectionCount), который отслеживает общее количество пересекающихся чисел, замеченных до сих пор;
4. После того, как итерация по второму списку завершена, у вас есть пересекающиеся числа в передней части LHM;
5. Теперь тривиально использовать numberSeen и intersectionCount и создать свой окончательный список.

Сложность во время выполнения снова равна O (m + n), а сложность пространства - O (n).

---

Исходный ответ:

Предполагая, что размер первого списка равен n , а размер второгоst это m , это простое и понятное решение, которое работает во времени O (m + n) и в пространстве O (m + n).

1. Возьмите второй список ипоместите все его элементы в хэш-карту, отображающую Integer в Integer.Это для отслеживания дубликатов в списке.Если в ваших списках нет дубликатов, просто используйте хэш-набор;
2. Теперь переберите первый список и для каждого элемента в списке:
   1. Если элемент существует на карте и имеетположительное число, поместите этот элемент в новый список и уменьшите его количество на карте;
   2. Если элемент не существует на карте или имеет число 0, перейдите к следующему элементу в списке.

В конце ваш новый список будет содержать пересечение двух списков в том порядке, в котором они появились в первом списке.

---

Общее пространство = m для хэш-карты + n для нового списка.

Общее время = m для размещения элементов в хэш-карте + n для итерации по первому списку.

Таким образом, O (m + n) время и O (m + n) пространство.

Answer 2

Как насчет:

LinkedHashSet<Integer> intersection = new LinkedHashSet<>(A).retainAll(new HashSet<>(B));

Или чтобы получить вывод в List:

List<Integer> intersection = new ArrayList<> (new LinkedHashSet<>(A).retainAll(new HashSet<>(B)));

На самом деле, этого, вероятно, достаточно сделать:

List<Integer> intersection = new ArrayList<> (A).retainAll(new HashSet<>(B));

, поскольку реализация retainAll вызывает contains переданного Collection, поэтому нам нужно только преобразовать B в HashSet, чтобы иметь постоянное время поиска.

РЕДАКТИРОВАТЬ:

Чтобы превратить предложенное решение в решение с линейным временем, вы должны воспользоваться HashSet временем поиска:

public static List Intersection(List<Integer> A, List<Integer> B) 
{
    List<Integer> outcome = new ArrayList<>();
    Set<Integer> BHashSet = new HashSet<>(B);
    for(Integer Aitem : A) {
        if(BHashSet.contains(Aitem)) {
            outcome.add(Aitem);
        }
    }

    return outcome;
}