algorithm - 在 4 个列表中查找一式三份

Question

我试图在给定 4 个 N 字符串数组的情况下，在 O(N*log(N)) 时间内找到一个字符串，该字符串对于至少 3 个数组是通用的，如果它存在，则返回按字典顺序排列的第一个字符串.

我尝试的是创建一个大小为 4*N 的数组，并从 4 个数组中添加项目，同时删除重复项。然后我对大数组进行了快速排序，以找到第一个最终的三次重复。

有人知道更好的解决方案吗？

Answer 1

您可以在 O(n log n) 中执行此操作，并具有恒定的额外空间。这是一个标准 k-way merge problem , 在对各个列表进行排序之后。如果单个列表可能包含重复项，则您需要在排序期间删除重复项。

因此，假设您有 list1、list2、list3 和 list4:

Sort the individual lists, removing duplicates
Create a priority queue (min-heap) of length 4
Add the first item from each list to the heap
last-key = ""
last-key-count = 0
while not done
    remove the smallest item from the min-heap
    add to the heap the next item from the list that contained the item you just removed.
    if the item matches last-key
        increment last-key-count
        if last-key-count == 3 then
            output last-key
            exit done
        else
            last-key-count = 1
            last-key = item key
end while
// if you get here, there was no triplicate item

另一种方法是将所有列表组合成一个列表，然后对其进行排序。然后您可以按顺序浏览它以找到第一个一式三份。同样，如果单个列表可能包含重复项，则应在合并列表之前将其删除。

combined = list1.concat(list2.concat(list3.concat(list4)))
last-key = ""
last-key-count = 0
for i = 0 to combined.length-1
    if combined[i] == last-key
        last-key-count++
        if last-key-count == 3
            exit done
        else
            last-key = combined[i]
            last-key-count = 1
end for
// if you get here, no triplicate was found