На сколько критичен сдвиг в массиве для алгоритмов?

Question

[AlexNew22]

Если я в обходе в массива каждый раз будут удалять из него значение из случайной позиции
Является ли это большей нагрузкой на алгоритм или редактирование массива таким способом не влияет на сложность нашего алгоритма?
Пример - у нас есть два массива с числами и нужно вывести массив, где будут все парные совпадения чисел
Есть мысль каждый раз удалять похожее число из второго массива при решении
Или как лучше решить подобную задачу не в лоб, а эффективно с точки зрения ресурсов?

arr1 = [1, 2, 4, 5, 1, 3]
arr2 = [8, 6, 1, 1, 3, 2, 9]
result = [1, 2, 1, 3]

Comments

[Alexandroppolus]

тебе надо создать новый массив, или удалить всё лишнее прямо из arr1, модифицировав оный?

[AlexNew22]

Alexandroppolus, надо вернуть новый массив в котором будут все повторяющиеся пары

[Alexandroppolus]

AlexNew22, тогда не думай про удаление. Просто напиши result = arr1.filter(...), а внутри колбэка делай проверку как посоветовал @wataru

хеш-таблица - это которая new Map, сотворенная из arr2, ключами будут числа, значениями - количества повторов

Answer 1

[Wataru]

Удаление из массива - медленно в общем случае. Если удалять хитро - поменяв элемент с последним и удалить с конца, то будет гораздо быстрее. Но это не во всех алгоритмах возможно.

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

Comments

[AlexNew22]

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

[Wataru]

AlexNew22,

Да, циклом. И да, это лучше. лучше один раз дополнительно пройтись циклом, зато потом сэкономить n циклов для поиска и удаления элемента.

[AlexNew22]

Wataru, спасибо
В таком случае сложность этого алгоритма будет O(2n)?

[Wataru]

AlexNew22, Почти. в O() константа не нужна, ведь O(2n) и O(10n) - это тоже что и O(n).

Answer 2

[Армянское Радио]

Зависит от того, массив это у вас, или, карта, или дек.
Удаление из массива занимает O(N) в худшем случае
Из карты - O(1)
Из дека O(bucket_size)

Вот и выбирайте

Answer 3

[mayton2019]

На проблему надо смотреть в комплексе. На самом деле еще важный вопрос - как вы найдете этот элемент в массиве. Это - тоже часть алгоритма.