根據另一個列表定義的順序對列表排序

Question

如何對列表中的元素進行排序A以便它們遵循另一個（超集）列表的排序B？假定沒有重複。

E.g. 甲可能包含[8 2 5 1]和乙可能含有[5 6 9 8 7 4 1 2 3]，所以我想進行排序甲成爲[5 8 1 2]

我很感興趣的方式有效地做到這一點，並具有良好的運行時複雜性。

Answer 1

如果乙是一個的超集，我只希望轉儲一個到一個哈希表，掃描乙並創建一個新的列表，其中我插入的每一個元素從乙即包含在哈希表中。使用O（a）額外的內存和O（b）運行時。

Answer 2

這裏有一些想法：（。在給出的時間複雜度，Ñ是大小甲和米是乙的大小的時間複雜性不簡化）

• 對於每個元素在乙，執行甲線性搜索，以查看是否該元素存在於其中。如果是這樣，請將其與A中尚未放置到位的第一個元素進行交換。 時間複雜度：O（nm）
• 同上，但首先將A的內容轉換爲高效的查找結構以避免線性搜索。 時間複雜度：O（n + m）假設O（1）查找
• 排序B。然後，對於A中的每個元素，使用二分搜索在B內找到其索引（其保證存在）。將該索引記錄在與A相同尺寸的輔助陣列中。使用該指數數組作爲比較器的輸入，該比較器對A進行排序。 時間複雜度：O（（M登入）+（N日誌N）+（N日誌N））