Найти уникальное отображение между элементами двух массивов одинакового размера

Question

Мне недавно задали этот вопрос в интервью:

Есть два массива размером 'n' каждый. У одного массива есть гайки, у другого болты. Каждая гайка соответствует ровно одному болту и наоборот. Когда вы сравниваете гайку с болтом, вы получаете один из 3 результатов: туго, свободно, подходит.

Как эффективно найти уникальное отображение?

Сортировка невозможна ни на одном из наборов. Вы никогда не знаете, если b1 меньше, чем b2 или
n1 меньше, чем n2. Где n1, n2 - гайки, а b1, b2 - болты. Единственное, что вы можете сделать, это сравнить гайку с болтом и получить результат: туго, подходит, свободно.

Answer 1

Алгоритм быстрой сортировки выполняет свою работу:

1. Случайно выбирает гайку n и использует ее как опору для разделения набора болтов B на три набора: туго (B1), свободный (B2), подходит.
2. Пометьте крепежный болт как b.Теперь вы используете этот болт в качестве шарнира для разделения набора гаек N\n на два набора: плотные (N1) или ослабленные (N2).
3. Теперь у вас есть три пары: N1 и B1, n и b, N2 и B2.Все они одинакового размера.Вы можете сделать то же самое рекурсивное разбиение на (N1,B2) и (N2,B1) и получить окончательный ответ.

Очевидно, сложность равна O(N log N), так же, как быстрая сортировка.

Answer 2

Для формального анализа (включая быструю сортировку) см. http://www.wisdom.weizmann.ac.il/~naor/PUZZLES/nuts_solution.html и http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/05-nutsbolts.pdf

Answer 3

Возьмите одну гайку N0 и сравните ее со всеми болтами.Получив информацию, мы можем разбить массив болтов на [bolts smaller than B0] + B0 + [bolts larger than B0].Всегда существует уникальный B0, который соответствует N0 на основании формулировки вопроса.

Затем возьмите следующий орех N1 и сравните его с B0.Если результат «жесткий», мы ищем меньшую половину, как мы делали выше с N0.В противном случае мы делаем то же самое, но с большей половиной.Выполнение этого еще больше разделит одну из двух половинок на 2.

Продолжайте делать это, пока вы не проработаете все гайки.Это эквивалентно быстрой сортировке.Средний случай - O (N logN), но есть очевидная сложность O (N ^ 2) в худшем случае, когда список уже «отсортирован».