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

Question

Виталий Ртищев @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'],
];

Вопрос задан более трёх лет назад
302 просмотра

13 комментариев

Подписаться 3 Средний 13 комментариев

Армянское Радио @gbg

Начать можно с того, чтобы отсортировать все номера лексикографически.

Написано более трёх лет назад
longclaps @longclaps

hint000, ты такой четкий... Но эту мелодию можно угадать с одной ноты.

Написано более трёх лет назад
uvelichitel @uvelichitel

hint000,
критерии оптимальности?
- не делать полного перебора квадратичной сложности O(n**2). И это представляется возможным. Примем метрикой расстояния между номерами D(номер1, номер2) количество отличающихся цифр. Тогда, например, если D(N1, N2) >2 и D(N2, N3)<2 то обязательно D(N1, N3)>1, N1 можно не сравнивать с N3. То есть очевидно можно не сравнивать каждый с каждым, можно избежать полного перебора.

Написано более трёх лет назад
longclaps @longclaps

uvelichitel, дорогой, ты тоже чоткий... но не надо меряться метриками. Покажи код.

Написано более трёх лет назад
uvelichitel @uvelichitel

Виталий Ртищев задачка интересная, но может переформулируйте/уточните условие в заголовке. Например "Как выбирать из справочника похожие номера?". Тогда, мне кажется вы привлечете больше алгоритмистов. Вопросы заданные в такой общей и несодержательной форме как у вас многие просто не открывают...

Написано более трёх лет назад
uvelichitel @uvelichitel

longclaps,
Покажи код.
Ага, USD35/час мой рейт, тогда код покажу.)) Я ж тоже чоткий...

Написано более трёх лет назад
longclaps @longclaps

uvelichitel, не смеши мои тапочки. знаток хаскеля. Есть простое решение О(NlogN), и для его описания можно обойтись даже словами. За базар тоже USD35/час просишь?

Написано более трёх лет назад
uvelichitel @uvelichitel

longclaps,
Есть простое решение О(NlogN)
Ну так приведите его хотя бы словами. Я плюсану. И на хабре могу вам плюсануть(у меня плюсовалка есть). На вопрос я подписался. Я понимаю что решение логарифмической сложности должно существовать. Мне это решение не известно, прежде чем искать его самому хочу послушать экспертов.

Написано более трёх лет назад

longclaps @longclaps

uvelichitel, даже линейный есть, если за память не париться. Python

data = ['1234', '1235', '2237', '3237', '2238', '2239']
for i in range(4):  # длина номера
    pairs = {}
    for s in data:
        t = s[:i] + s[i + 1:]
        l = pairs.get(t, [])
        l.append(s)
        pairs[t] = l
    for l in pairs.values():
        if len(l) > 1:
            print(*l)

выхлоп

2237 3237
1234 1235
2237 2238 2239

Написано более трёх лет назад

uvelichitel @uvelichitel

longclaps, Хорошо. Но кажется некорректно - попробуйте добавить '2337' в data.

Написано более трёх лет назад
longclaps @longclaps
uvelichitel,
2237 3237 2237 2337 1234 1235 2237 2238 2239
Написано более трёх лет назад
uvelichitel @uvelichitel

longclaps, Хорошо. Куда плюсануть?))

Написано более трёх лет назад
longclaps @longclaps

uvelichitel, да не к спеху, будет нужно - позову )

Написано более трёх лет назад

Решения вопроса 1

3 комментария

longclaps @longclaps

Толковое толкование. Я так, наверное, никогда не научусь. Но в комментариях к вопросу решение есть.
В любом случае с почином.

Написано более трёх лет назад
GreenBear @GreenBear

longclaps, спасибо! Только сейчас заметил, что у вопросов еще и комментарии есть.
У вас там все ч0тко!

Написано более трёх лет назад
Дмитрий Макаров @DmitryITWorksMakarov

Прикольно!

Предлагаю докрутить. Из номеров будем не убирать символ, а заменять на "Х" - тогда нам будет нужен только один словарь. А перед тем как положить очередной номер в кучку похожих номеров, выдать пары между новым и лежащими в кучке.

Написано более трёх лет назад

Пригласить эксперта

Ответы на вопрос 1

Комментировать

Ваш ответ на вопрос

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

Войти через центр авторизации

Похожие вопросы

Алгоритмы

Простой
Какую формулу использовать?
- 1 подписчик
- 18 часов назад
- 94 просмотра
3

ответа
C++

+1 ещё

Простой
Рекурсивный ввод-вывод последовательности без использования массивов и списоков?
- 2 подписчика
- 22 часа назад
- 406 просмотров
1

ответ
Алгоритмы

Средний
Справится ли алгоритм с задачей по поиск слов в словаре?
- 1 подписчик
- 17 апр.
- 71 просмотр
1

ответ
Алгоритмы

Простой
Как определить сложность алгоритма?
- 1 подписчик
- 16 апр.
- 101 просмотр
3

ответа
Алгоритмы

+2 ещё

Простой
Какая может быть формула для решения этой задачи?
- 3 подписчика
- 11 апр.
- 5379 просмотров
3

ответа
Алгоритмы

+1 ещё

Простой
Как узнать, входит ли игрок1 (x,y,z) в поле игрок2 (x,y,z)?
- 1 подписчик
- 08 апр.
- 190 просмотров
3

ответа
C++

+1 ещё

Простой
Как решить данную задачу при помощи префиксного дерева?
- 2 подписчика
- 05 апр.
- 196 просмотров
1

ответ
Алгоритмы

+1 ещё

Средний
Есть ли современная реализации алгоритма триангуляции невыпуклого многоугольника с отверстиями?
- 1 подписчик
- 29 мар.
- 108 просмотров
0

ответов
JavaScript

+1 ещё

Средний
Как найти начальную точку для определения маршрутов в двумерном массиве?
- 1 подписчик
- 15 мар.
- 227 просмотров
6

ответов
Алгоритмы

+1 ещё

Простой
Как объединить списки, полученные от 2 REST API с параметрами `limit` и `offset`, и вернуть его, согласно параметрам `limit` и `offset`?
- 1 подписчик
- 15 мар.
- 105 просмотров
2

ответа
Показать ещё Загружается…

С developer (алгоритмист)

СберТех • Москва

от 350 000 ₽

Бэкенд программист

Grade Factor • Москва

от 80 000 ₽

Senior Java Developer, Database Engine

CedrusData

от 350 000 ₽

Скопировать сайт

19 апр. 2024, в 17:06

15000 руб./за проект

Поправить пхп скрипт

19 апр. 2024, в 16:53

1000 руб./за проект

Требуется настройка Яндекс Директа

19 апр. 2024, в 16:45

5000 руб./за проект

Начать можно с того, чтобы отсортировать все номера лексикографически.
hint000, ты такой четкий... Но эту мелодию можно угадать с одной ноты.
hint000,
критерии оптимальности?
- не делать полного перебора квадратичной сложности O(n**2). И это представляется возможным. Примем метрикой расстояния между номерами D(номер1, номер2) количество отличающихся цифр. Тогда, например, если D(N1, N2) >2 и D(N2, N3)<2 то обязательно D(N1, N3)>1, N1 можно не сравнивать с N3. То есть очевидно можно не сравнивать каждый с каждым, можно избежать полного перебора.
uvelichitel, дорогой, ты тоже чоткий... но не надо меряться метриками. Покажи код.
Виталий Ртищев задачка интересная, но может переформулируйте/уточните условие в заголовке. Например "Как выбирать из справочника похожие номера?". Тогда, мне кажется вы привлечете больше алгоритмистов. Вопросы заданные в такой общей и несодержательной форме как у вас многие просто не открывают...
longclaps,
Покажи код.
Ага, USD35/час мой рейт, тогда код покажу.)) Я ж тоже чоткий...
uvelichitel, не смеши мои тапочки. знаток хаскеля. Есть простое решение О(NlogN), и для его описания можно обойтись даже словами. За базар тоже USD35/час просишь?
longclaps,
Есть простое решение О(NlogN)
Ну так приведите его хотя бы словами. Я плюсану. И на хабре могу вам плюсануть(у меня плюсовалка есть). На вопрос я подписался. Я понимаю что решение логарифмической сложности должно существовать. Мне это решение не известно, прежде чем искать его самому хочу послушать экспертов.
uvelichitel, даже линейный есть, если за память не париться. Python
data = ['1234', '1235', '2237', '3237', '2238', '2239'] for i in range(4): # длина номера pairs = {} for s in data: t = s[:i] + s[i + 1:] l = pairs.get(t, []) l.append(s) pairs[t] = l for l in pairs.values(): if len(l) > 1: print(*l)

выхлоп
2237 3237 1234 1235 2237 2238 2239
longclaps, Хорошо. Но кажется некорректно - попробуйте добавить '2337' в data.
uvelichitel, да не к спеху, будет нужно - позову )

Answer 1 · 2019-08-08 19:16:55

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

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

Такой алгоритм будет работать некорректно, если изначально есть полностью идентичные номера, но если я правильно понял, изначально они все разные.

Answer 2 · 2019-08-08 15:54:43

Положить все номера в хэш-таблицу.
start: Берем первый непомеченный номер и, начиная с него, делаем поиск в ширину по всем соседям (их меньше либо равно 20).
Если сосед найден, то выписываем эту пару.
Когда у очередного номера найдены все соседи, то помечаем его.
Следующую итерацию поиска проводим только для непомеченных соседей.
Повторяем, начиная со start`а, пока есть непомеченные номера.

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

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

Минуточку внимания

Войдите на сайт