@AlexNew22

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

Если я в обходе в массива каждый раз будут удалять из него значение из случайной позиции
Является ли это большей нагрузкой на алгоритм или редактирование массива таким способом не влияет на сложность нашего алгоритма?
Пример - у нас есть два массива с числами и нужно вывести массив, где будут все парные совпадения чисел
Есть мысль каждый раз удалять похожее число из второго массива при решении
Или как лучше решить подобную задачу не в лоб, а эффективно с точки зрения ресурсов?
arr1 = [1, 2, 4, 5, 1, 3]
arr2 = [8, 6, 1, 1, 3, 2, 9]
result = [1, 2, 1, 3]
  • Вопрос задан
  • 119 просмотров
Решения вопроса 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Удаление из массива - медленно в общем случае. Если удалять хитро - поменяв элемент с последним и удалить с конца, то будет гораздо быстрее. Но это не во всех алгоритмах возможно.

Но самое быстрое решение вашей задачи будет положить один массив в хеш таблицу, и при проходе по второму проверять, есть ли текущий элемент в таблице. Для борьбы с повторяющимеся элементами вв таблице по ключу храните счётчик одинаковых элементов и уменьшайте его при нахождении совпадения.
Ответ написан
gbg
@gbg
Любые ответы на любые вопросы
Зависит от того, массив это у вас, или, карта, или дек.
Удаление из массива занимает O(N) в худшем случае
Из карты - O(1)
Из дека O(bucket_size)

Вот и выбирайте
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
mayton2019
@mayton2019
Bigdata Engineer
На проблему надо смотреть в комплексе. На самом деле еще важный вопрос - как вы найдете этот элемент в массиве. Это - тоже часть алгоритма.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы