Найти связанный список группу внутри другой связанного список группы

Question

у меня есть этот класс:

public class IntNode { 
private int _value; 
private IntNode _next; 
public IntNode(int val, IntNode n) { 
_value = val; 
_next = n; 
} 
public int getValue() { 
return _value; 
} 
public IntNode getNext() { 
return _next; 
} 
public void setValue(int v) { 
_value = v; 
} 
public void setNext(IntNode node) { 
_next = node; 
} 
} 

и это:

public class IntList { 
private IntNode _head; 
public IntList() { 
_head = null; 
} 
public IntList (IntNode node) { 
_head = node; 
} 
. . . // methods 
} 

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

Мне нужно добавить функцию public boolean isSubset (IntList other), которые возвращают true, если группа является подгруппой списка или false в противном случае. , например:

А = {1, 4, 2, 8}

В = [4, 8}

так A.isSubset(B) возвращение истинного и B.isSubset(A) возвращение ложным. Эта функция должна быть максимально эффективной.

Я знаю, что могу проверить каждое число из группы, получившуюся в качестве параметра, и найти этот номер внутри другого списка и снова проверить следующий номер и повторить цикл по всему списку, но это будет O (n²), чтобы он не будет настолько эффективным. может быть какое-то другое решение?

Answer 1

Я бы предложил отсортировать списки по алгоритму qicksort и затем выполнить поиск элементов по бинарному поиску.

Здесь вы можете посмотреть на соответствующие темы Википедии:

Wiki - Quicksort

Wiki - Binary Search