比較兩個列表

Question

的排序是否有一個算法比爲O（n^2）重新排序列表2更好地匹配列表1

表1：ABCD

表2：BDCA

注：表2可以有更多的，更少甚至完全不同的項目相比列表1.

Answer 1

如果你可以創建一個總排序在列表中的項目的類型，那麼你可以通過創建一個列表索引1整理項目。然後，您可以使用此索引重新排列列表2.該算法在時間上是O（n log n），並且在空間中需要額外的O（n）。這將導致爲O

Answer 2

一種可能性（N日誌（n））的是以下內容。這要求將列表值讀入陣列/矢量/可排序類型的結構中：

• 根據值排序列表1並保留位置信息。這提供了一種快速查找項目並瞭解其位置的方法。用於排序的成本是O使用從第一步的比較功能排序列表（N log n）的
• 排序列表2。兩個比較兩個值，在排序列表1結果中查找它們，並使用相對位置作爲兩個值之間的比較。這種成本也是O（n log n）。

編輯之後，您提到第二個列表可能與第一個列表沒有關聯。所以比較功能必須考慮到這一點。如果被比較的一個或兩個值不在第一個列表中，那麼比較功能需要決定對值進行排序（例如，它們是在最後還是開始？）。

Answer 3

您正在尋找Diff Algorithm！