CodeLAB
на главную карта сайта обратная связь

Популярные задачи:

#Вычисление значения полинома. (63370 hits)
#Обновление нескольких записей таблицы. (33376 hits)
#Случайный выбор нескольких несовпадающих значений из множества. (60109 hits)
#Динамическое изменение цвета полоски прокрутки в IE5.5 и выше. (31702 hits)
#Создание простейшей таблицы. (38022 hits)
#ООП на javascript: классы, наследование, инкапсуляция. (259338 hits)
#Подсветка синтаксиса. (32316 hits)
#"C# и платформа .NET" Эндрю Троелсен (Andrew Troelsen, "C# and the .NET platform"), листинги, код, примеры из книги, исходники. (39911 hits)
#Летающие, крутящиеся шарики. (45626 hits)
#Рисование линии (по Брезенхэму). (34847 hits)
#Рисование Фрактала (листьев папоротника). (54129 hits)
#Поразрядная сортировка, общий принцип. (132707 hits)
#Преобразование RGB в HEX и обратно HEX в RGB. (57828 hits)
#Счетчик времени с точностью до микросекунд. (130739 hits)
#Обработка шаблонных писем. (56563 hits)
#Простой генератор случайных чисел. (135541 hits)
#сортировка пузырьком. (154694 hits)
#Арктангенс. (46595 hits)
#Двусторонняя карта. (34872 hits)
#Рисование множества Мандельброта. (45563 hits)
показать все >>


Главная >> Каталог задач >> Последовательности >>

Найти общие элементы в списках

Aвтор:
Дата:
Просмотров: 986
реализации +добавить

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

Следует подчеркнуть что поскольку мы имеем дело со Связными списками (а не массивами), то можем только последовательно друг за другом читать оттуда элементы, а не по индексу как обычно с массивами. Т.е. у нас для входных данных доступна по сути только одна операция типа next (взять следующий элемент) , которая возвращает следующий элемент этого списка или например null (пустое значение) если мы достигли конца списка. И всё, как говорится, крутись как хочешь )

Перебором

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

Что с производительностью такого решения? Ну очевидно что т.к. у нас 2 вложенных цикла, первый размером N и второй -  M то это получается квадратичная скорость, т.е. O(N*M) в худшем случае что конечно медленно.

Псевдокод перебором

Получаем примерно такой:

 псевдокод: найти общие элементы в списках перебором  ссылка
  1. list1 = <input1>
  2. list2 = <input2>
  3. result = new list
  4.  
  5. for each element from list1 do:
  6.   current = element
  7.   for each element2 from list2 do:
  8.     if current == element2 then:
  9.       result.add(current)
  10.       // далее просто останавливаем цикл по list2
  11.       break; 
  12.  
  13. return result

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

Быстрее?

Что ж, с медленным вариантом разобрались, довольно просто, а можем ли как-то быстрее?
Ну без изменения начальных условий или структуры исходных данных - очевидно что нет. 

А давайте поразмыслим немного как именно мы ищем в нашем медленном варианте перебором: мы проходимся по всем элементам первого списка и на каждом шаге ищем этот элемент во втором списке. При этом ищем его самым тривиальным и простым способом - последовательным поиском который занимает линейное время ( ~O(N) - где N это размер всего списка) и проходит по каждому элементу второго списка. 
А какие еще варианты? Вмысле какие еще методы поиска у нас есть?

Да, именно, ну конечно - бинарный поиск , скорость которого уже логарифмичная т.к. O(ln N), а это считай на порядок быстрее чем линейный. 
Круто давайте его и применим для поиска элемента во втором списке.

Реализации:

нет на данный момент   +добавить