在没有重复的情况下创建两个字符串数组的联合

Question

我刚刚写了我的考试，其中一个问题希望我们得到 A[] 大小 N 和 B[] 大小 N 的并集并删除重复项（A 和 B 可以在它们自身中有重复项）并将其放入Z[] 大小为 2N。我们只是被要求为此提供伪代码，但它是一个 c++ class。

我们被要求在不使用堆 space 的情况下制作这个版本的两个版本（除了常量时间局部变量之外不创建新的数组或数据结构），另一个没有限制。此外，两者都是最快的运行时间。

有限制的我只能用嵌套 for 循环使它成为 O(N^2) 并且只是迭代 Z[] 因为我将元素从 A 和 B 放入 Z。

这个是我对你的家伙更感兴趣的 opinion/what 你会做吗（对于没有限制的那个）：

我得到以下（运行时间 O(NlogN)）：

创建一个大小为 2N 的数组 E 将 A 和 B 中的所有内容放入 E - O(N)

合并排序 E // 使用 ascii 排序 - O(NlogN)

String previous

for loop from i = 0 to sizeOfE  { - O(N)

if previous does not equal E[i] then add to Z[] and the string previous equals E[i] - O(1)

}

这是最快的吗way/is对吗？你会怎么做这道题？

Answer 1

对于第一个选项，我将扫描 A 以找到其中一半值低于一半值的值。然后我会把那个值放在中间，把较低的值放在左边，较高的值放在右边，同时扔掉任何匹配的值。这可以在不创建新数组的情况下完成。然后我会在两个子阵列上重复。这是一个改进的快速排序，所以它是 O(nlog(n))

然后我会和B一起重复

然后我会将两者合并到 Z，这是一个复杂度为 O(n) 的操作，但是如果 A 中的值与 B 中的值匹配，则两者的合并将省略一个值。

所以整个事情是 O(nlog(n)).

对于没有限制的，我会先对 A 然后对 B 进行直接合并排序，除非合并时，如果某个值与先前插入的值匹配，则忽略该值，并且在整个合并排序过程中都这样做。这会更快一些，因为在某些情况下重复项会被更快地删除。总的来说归并排序也是 O(nlog(n)).

在没有重复的情况下创建两个字符串数组的联合

Create the Union of two String Arrays while having no duplicates

c++

arrays

sorting

pseudocode