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

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

Существует два массива размером "n". Один массив имеет гайки, другой - болты. Каждая гайка подходит ровно к одному болту и наоборот. Когда вы сравниваете гайку с болтом, вы получаете один из трех результатов: плотный, рыхлый, подходит.

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

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

Ответы

Ответ 1

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

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

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

Ответ 2

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

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

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