Мне задали этот вопрос:
Вам даны два списка целых чисел, каждый из которых отсортирован в порядке возрастания, и каждый из которых имеет длину n. Все целые числа в двух списках разные. Вы хотите найти n-й наименьший элемент объединения двух списков. (То есть, если вы объединили списки и отсортировали итоговый список в порядке возрастания, элемент, который будет находиться на n-й позиции.)
Мое решение:
Предположим, что списки индексируются 0
O (n) раствор :
Прямое решение состоит в том, чтобы наблюдать, что массивы уже отсортированы, поэтому мы можем объединить их и остановиться после n шагов. Первые n-1 элементы не нужно копировать
в новый массив, поэтому это решение занимает O (N) времени и O (1) памяти.
O (log2 n) решение :
Решение O (log2 n) использует альтернативный бинарный поиск в каждом списке. Короче говоря, он берет средний элемент в текущем интервале поиска в первом списке (l1 [p1]) и ищет его в l2. Поскольку элементы уникальны, мы найдем не более 2 значений, ближайших к l1 [p1]. В зависимости от их значений относительно l1 [p1-1] и l1 [p1 + 1] и их индексов p21 и p22, мы либо возвращаем n-й элемент, либо возвращаем: если сумма любого из (максимум) 3 индексы в l1 можно комбинировать с одним из (не более) 2 индексов в l2, так что l1 [p1 '] и l2 [p2'] будут находиться рядом друг с другом в отсортированном объединении двух списков, а p1 '+ p2 '= n или p1' + p2 '= n + 1, мы возвращаем один из 5 элементов. Если p1 + p2> n, мы возвращаемся к левой половине интервала поиска в l1, в противном случае мы возвращаемся к правому интервалу. Таким образом, для O (log n) возможных середин в l1 мы делаем O (log n) бинарный поиск в l2. Следовательно, время работы O (log2 n).
O (log n) решение :
Предполагая, что списки l1 и l2 имеют постоянное время доступа к любому из их элементов, мы
можно использовать модифицированную версию бинарного поиска, чтобы получить решение O (log n). Самый простой подход состоит в том, чтобы искать индекс p1 только в одном из списков и вычислять соответствующий индекс p2 в другом списке так, чтобы p1 + p2 = n всегда. (Предполагается, что списки проиндексированы с 1.)
Сначала мы проверяем особый случай, когда все элементы одного списка меньше, чем любой элемент в другом списке:
Если l1 [n]
findNth(start,end)
p1 = (start + end)/2
p2 = n-p1
if l1[p1] < l2[p2]:
if l1[p1 + 1] > l2[p2]:
return l2[p2]
else:
return findNth(p1+1, end)
else:
if l2[p2 + 1] > l1[p1]:
return l1[p1]
else:
return findNth(start,p1-1)
Элемент l2 [p2] возвращается, когда l2 [p2] больше, чем точно p1 + p2-1 = n-1 элементов
(и, следовательно, является n-м наименьшим). l1 [p1] возвращается при тех же, но симметричных условиях. Если l1 [p1]
Интервьюер постоянно спрашивает меня о разных подходах к вышеуказанной проблеме. Я предложил три вышеупомянутых подхода. Верны ли они? Есть ли какое-либо иное наилучшее решение для этого вопроса? На самом деле этот вопрос задавался много раз, поэтому, пожалуйста, предоставьте несколько хороших вещей об этом.