Найдите общие элементы в двух отсортированных списках в линейное время

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

Следующий текст также хвостовой рекурсивный (насколько я могу судить), но выходной список, следовательно, перевернут:

let rec merge xs ys acc =
    match (xs, ys) with
    | ((x :: xt), (y :: yt)) ->
        if x = y then
            let rec count_and_remove_leading zs acc =
                match zs with
                | z :: zt when z = x -> count_and_remove_leading zt (acc + 1)
                | _ -> (acc, zs)
            let rec replicate_and_prepend zs n =
                if n = 0 then
                    zs
                else
                    replicate_and_prepend (x :: zs) (n - 1)
            let xn, xt = count_and_remove_leading xs 0
            let yn, yt = count_and_remove_leading ys 0
            merge xt yt (replicate_and_prepend acc (xn * yn))
        else if x < y then
            merge xt ys acc
        else
            merge xs yt acc
    | _ -> acc

let xs = [2; 4; 6; 8; 8; 10; 12]
let ys = [-7; -8; 2; 2; 3; 4; 4; 8; 8; 8;]
printf "%A" (merge xs ys [])

Выход:

[8; 8; 8; 8; 8; 8; 4; 4; 2; 2]

Обратите внимание, что, как говорит sdcvvc в своем ответе, это все еще O (x.length * y.length) в худшем случае просто потому, что крайний случай двух списков повторяющихся идентичных элементов потребует создания значений x.length * y.length в выходном списке, что само по себе является операцией O (m * n) .

Я не знаю F #, но могу предоставить функциональную реализацию Haskell, основанную на алгоритме, описанном tvanfosson (дополнительно определенным Лассе В. Карлсеном).

import Data.List

join :: (Ord a) => [a] -> [a] -> [a]
join l r = gjoin (group l) (group r)
  where
    gjoin [] _ = []
    gjoin _ [] = []
    gjoin l@(lh@(x:_):xs) r@(rh@(y:_):ys)
      | x == y    = replicate (length lh * length rh) x ++ gjoin xs ys
      | x < y     = gjoin xs r
      | otherwise = gjoin l ys

main :: IO ()
main = print $ join [2, 4, 6, 8, 8, 10, 12] [-7, -8, 2, 2, 3, 4, 4, 8, 8, 8]

Это печатает [2,2,4,4,8,8,8,8,8,8] . На случай, если вы не знакомы с Haskell, некоторые ссылки на документацию:

• группа
• длина
• реплицировать

Я думаю, что это можно сделать, просто используя хеш-таблицы. В хеш-таблицах хранится частота элементов в каждом списке. Затем они используются для создания списка, в котором частота каждого элемента e равна частоте e в X, умноженной на частоту e в Y. Это имеет сложность O (n + m).

(EDIT: только что заметил что это может быть худший случай O (n ^ 2), после прочтения комментариев к другим сообщениям. Нечто подобное уже было опубликовано. Извините за дубликат. Я сохраняю сообщение на случай, если код поможет.)

Я не знаю F #, поэтому прилагаю код Python. Я надеюсь, что код будет достаточно читабельным, чтобы его можно было легко преобразовать в F #.

def join(x,y):
    x_count=dict() 
    y_count=dict() 

    for elem in x:
        x_count[elem]=x_count.get(elem,0)+1
    for elem in y:
        y_count[elem]=y_count.get(elem,0)+1

    answer=[]
    for elem in x_count:
        if elem in y_count:
            answer.extend( [elem]*(x_count[elem]*y_count[elem] ) )
    return answer

A=[2, 4, 6, 8, 8, 10, 12]
B=[-8, -7, 2, 2, 3, 4, 4, 8, 8, 8]
print join(A,B)

Проблема с тем, что он хочет, в том, что это, очевидно, должно быть повторно пройти по списку.

Чтобы 8,8,8 отображались дважды, функция должна пройти немного по второму списку. В худшем случае (два идентичных списка) все равно будет получено O (x * y)

Обратите внимание, что при этом не используются внешние функции, которые зацикливаются сами по себе.

for (int i = 0; i < shorterList.Length; i++)
{
    if (shorterList[i] > longerList[longerList.Length - 1])
        break;
    for (int j = i; j < longerList.Length && longerList[j] <= shorterList[i]; j++)
    {
        if (shorterList[i] == longerList[j])
            retList.Add(shorterList[i]);
    }
}

Я думаю, что это O (n) в коде пересечения / соединения, хотя полный обход проходит каждый список дважды:

// list unique elements and their multiplicity (also reverses sorting)
// e.g. pack y = [(8, 3); (4, 2); (3, 1); (2, 2); (-8, 1); (-7, 1)]
// we assume xs is ordered
let pack xs = Seq.fold (fun acc x ->
    match acc with
    | (y,ny) :: tl -> if y=x then (x,ny+1) :: tl else (x,1) :: acc
    | [] -> [(x,1)]) [] xs

let unpack px = [ for (x,nx) in px do for i in 1 .. nx do yield x ]

// for lists of (x,nx) and (y,ny), returns list of (x,nx*ny) when x=y
// assumes inputs are sorted descending (from pack function)
// and returns results sorted ascending
let intersect_mult xs ys =
    let rec aux rx ry acc =
        match (rx,ry) with
        | (x,nx)::xtl, (y,ny)::ytl -> 
            if x = y then aux xtl ytl ((x,nx*ny) :: acc)
            elif x < y then aux rx ytl acc
            else aux xtl ry acc
        | _,_ -> acc
    aux xs ys []

let inner_join x y = intersect_mult (pack x) (pack y) |> unpack

Теперь мы проверим его на ваших данных образца

let x = [2; 4; 6; 8; 8; 10; 12]
let y = [-7; -8; 2; 2; 3; 4; 4; 8; 8; 8;]

> inner_join x y;;
val it : int list = [2; 2; 4; 4; 8; 8; 8; 8; 8; 8]

РЕДАКТИРОВАТЬ: Я только что понял, что это та же идея, что и в предыдущем ответе sdcvvc (после редактирования).

Вы не можете получить O (min (x.length, y.length) ), потому что выход может быть больше. Предположим, например, что все элементы x и y равны. Тогда выходной размер является произведением размера x и y, что дает нижнюю границу эффективности алгоритма.

Вот алгоритм на F #. Это не хвостовая рекурсия, что легко исправить. Хитрость заключается в взаимной рекурсии. Также обратите внимание, что я могу инвертировать порядок списка, переданного в prod , чтобы избежать ненужной работы.

let rec prod xs ys = 
    match xs with
    | [] -> []
    | z :: zs -> reps xs ys ys
and reps xs ys zs =
    match zs with
    | [] -> []
    | w :: ws -> if  xs.Head = w then w :: reps xs ys ws
                 else if xs.Head > w then reps xs ys ws
                 else match ys with
                      | [] -> []
                      | y :: yss -> if y < xs.Head then prod ys xs.Tail else prod xs.Tail ys

Исходный алгоритм в Scala:

def prod(x: List[Int], y: List[Int]): List[Int] = x match {
  case Nil => Nil
  case z :: zs => reps(x, y, y)
}

def reps(x: List[Int], y: List[Int], z: List[Int]): List[Int] = z match {
  case w :: ws if x.head == w => w :: reps(x, y, ws)
  case w :: ws if x.head > w => reps(x, y, ws)
  case _ => y match {
    case Nil => Nil
    case y1 :: ys if y1 < x.head => prod(y, x.tail)
    case _ => prod(x.tail, y)
  }
}