Извлечение элементов из одного массива из другого массива

Question

У меня вопрос, который задают в интервью.

Имеется 2 массива.

arr1 = {3,5,6,8,1,6,7}; 
arr2 = {5,6,8}; 

поэтому окончательный вывод

arr1 = {3,8,1,7}; 

Я мог бы ответить на него O(n^2) время.

Есть ли лучший способ сделать это.

Привет,

Раджеш

Answer 1

Вы можете сделать это в O (N + M) времени путем построения HashSet из второго массива, чтобы использовать в качестве поиска. Эти поисковые запросы выполняются в O (1), и для построения набора требуется O (m).

Затем вы просто перебираете свой первый массив в O (n) и сохраняете только нужные элементы.

Answer 2

Вы можете сделать это в O(n) с помощью HashSet. Добавьте второй элементы массива в HashSet и итерации первого массива в один проход -

Это даст вам O (N)

Внедрение в Java ниже. Пожалуйста, игнорируйте опечатки

int[] arr2 = {5,6,8}; 
Set toBeRemoved = new HashSet<Integer>(); 
for(int i:arr2){ 
toBeRemoved.add(i); 
} 
for(int i:arr1){ 
if(toBeRemoved.contains(i)){ 
//Logic to remove from array 
//Or else if you dont have space contraint just add elements to a new array 
} 
}