Медиана списков

Question

Я задал этот вопрос:

Вам предоставляется два списка целых чисел, каждое из которых сортируется в порядке возрастания, и каждый из которых имеет длину п. Все целые числа в двух списках различны. Вы хотите найти n-й наименьший элемент объединения двух списков. (То есть, если вы объединили списки и отсортировали результирующий список в порядке возрастания, элемент, который будет находиться в n-й позиции.)

Предположим, что списки индексируются 0.

О (п) решение: Прямой вперед решение заметить, что массивы уже отсортированы, так что мы можем объединить их, и остановится после п шагов. Первым элементам 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 (журнал п) решения: Предполагая, что списки l1 и l2 имеют постоянное время доступа к любому из их элементов, мы можно использовать модифицированную версию двоичного поиска, чтобы получить O (журнал п) решения. Самый простой способ - найти индекс p1 только в одном из списков и вычислить соответствующий индекс p2 в другом списке, чтобы p1 + p2 = n всегда. (Это предполагает, что списки индексируются из 1.) Сначала мы проверяем специальный случай, когда все элементы одного списка меньше любого элемента в другом списке: Если l1 [n] < l2 [0] return l1 [n ]. Если l2 [n] < l1 [0] return l2 [n]. Если мы не находим п-й наименьший элемент после этого шага, вызовите findNth (1, п) с приближенным псевдокоде:

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] < l2 [p2] и l1 [p1 + 1] < l2 [p2], ранг l2 [p2] больше n, поэтому нам нужно взять больше элементов из l1 и меньше от l2. Поэтому мы ищем p1 в верхней половине предыдущего интервала поиска. С другой стороны, если l2 [p2] < l1 [p1] и l2 [p2 + 1] < l1 [p1], ранг l1 [p1] больше n. Поэтому реальный p1 будет лежать в нижней половине нашего текущего интервала поиска. Поскольку мы уменьшаем вдвое размер проблемы при каждом вызове findNth, и нам нужно делать только постоянную работу, чтобы уменьшить размер проблемы вдвое, повторение для этого алгоритма T (n) = T (n/2) + O (1), который имеет решение O (log n) -time.

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

Answer 1

Не уверен, что если вы взглянули на это: http://www.leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html

Это решать более обобщенный вариант задачи вы просите о. Возможна определенная сложность журнала ...

Answer 2

Я думаю, что это будет лучшее решение. ,

->1 2 3 4 5 6 7 8 9 
->10 11 12 13 14 15 16 17 18 

принимают два указателя я и J каждый из которых указывает на начало массива, приращение I, если а [I] < б [J]

приращение J, если а [я]> б [J ]

сделайте это n раз.

линейное решение O (n) O (1).