vitalyrtishchev
@vitalyrtishchev
Frontend разработчик

Какой алгоритм подойдет для наиболее оптимального решения задачи?

Напишите функцию, принимающую массив из строк, содержащих номер телефона в формате +7 (XXX) XXX-XX-XX. Функция должна вернуть пары номеров, которые отличаются одной цифрой.

Например,
getPhonePairs([
  '+7 (985) 111-11-11',
  '+7 (985) 111-11-12',
  '+7 (985) 111-11-22',
]);

// ->
[
  ['+7 (985) 111-11-11', '+7 (985) 111-11-12'],
  ['+7 (985) 111-11-12', '+7 (985) 111-11-22'],
];
  • Вопрос задан
  • 211 просмотров
Решения вопроса 1
@GreenBear
Если два номера "похожи", значит у них есть ровно один отличающийся символ, который расположен в той же самой позиции. Это значит, если у всех номеров удалить символ из конкретной позиции, то все "похожие" номера станут идентичными между собой. А значит их можно собрать в словарь, где ключ - это урезанный номер, а значение - это массив неурезанных "похожих" номеров.

В номере 11 значащих символов. Убираем сначала у всех первый символ, получаем первый словарь с похожими номерами.
Потом из начальных номеров убираем второй символ, и получаем второй словарь с "похожими номерами" по второй позиции.
И так делаем 11 раз, пока у нас не получится 11 словарей.
Далее из каждого словаря остается выбрать только те значения, в которых более одного элемента в массиве.
Останется только составить пары номеров, взятых из этих массивов.

Такой алгоритм будет работать некорректно, если изначально есть полностью идентичные номера, но если я правильно понял, изначально они все разные.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
longclaps
@longclaps
Для наиболее оптимального решения задачи подойдёт наиболее оптимальный алгоритм. То есть это тавтология, нужно говорить так: для оптимального решения задачи подойдёт оптимальный алгоритм.
Наиболее оптимальный - это перебор. Не в том смысле, что оптимальным является алгоритм перебора (нет, это не так), но в том смысле, что это чересчур. Андыстэнд?
Ответ написан
DmitryITWorksMakarov
@DmitryITWorksMakarov
Положить все номера в хэш-таблицу.
start: Берем первый непомеченный номер и, начиная с него, делаем поиск в ширину по всем соседям (их меньше либо равно 20).
Если сосед найден, то выписываем эту пару.
Когда у очередного номера найдены все соседи, то помечаем его.
Следующую итерацию поиска проводим только для непомеченных соседей.
Повторяем, начиная со start`а, пока есть непомеченные номера.
Ответ написан
Ваш ответ на вопрос

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

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