c++ - 建议一个合适的算法来合并两个包含类对象的数组(不重复)

Question

我有一个数组，其中每个位置都包含一个具有三个 int 值 (x,y,z) 的类对象。现在必须从不同的数组中将所有元素复制到源数组中。对于每个数组元素，我们需要检查 x、y、z 值以避免重复。有没有可能比 o(n^2) 更有效？

Answer 1

前提是你不介意丢失两个数组原来的顺序:

std::sort(first_array, first_array + N);
std::sort(second_array, second_array + M);
std::set_union(
    first_array, first_array+N, 
    second_array, second_array+M, 
    target_array
);

N和 M是数组中元素的数量。您需要定义 operator<或专攻 std::less对于你的类(class):或者编写一个比较器函数并将其提供给 sort和 set_union .

时间复杂度为O(N log N + M log M) -- sort是较慢的部分，然后是 set_union是线性的。

如果first_array或 second_array可能已经在它们内部(不仅仅是它们之间)包含了重复项，那么你需要一个额外的步骤来删除它们，这不仅会丢失顺序，还会丢失源数组中的重复项:

std::sort(first_array, first_array + N);
MyClass *first_end = std::unique(first_array, first_array + N);
std::sort(second_array, second_array + M);
MyClass *second_end = std::unique(second_array, second_array + M);
std::set_union(
    first_array, first_end, 
    second_array, second_end, 
    target_array
);

或者，您可以编写 set_union 的修改版本在一次通过中进行合并和重复数据删除。

[编辑:抱歉，在写这篇文章时我错过了结果最终会回到 first_array , 不成单独的 target_array . set_union不适用于将输出作为输入之一，因此这也需要目标数组的额外内存，然后可以将其复制回源数组，当然前提是源足够大。]

如果你确实想保留原始数组的顺序，那么你可以创建一个容器并在进行时检查:

container<MyClass> items(first_array, first_array + N);
MyClass *dst = first_array + N;
for (MyClass *it = second_array; it != second_array + M; ++it) {
    if (items.count(*it) == 0) {
        items.insert(*it);
        *dst++ = *it;
    }
}

如果数组本身可以包含重复项，则以 items 开头空和 dst = first_array ，然后遍历两个输入数组。

container可能是 std::set (在这种情况下时间是 O(N log N + M log(N + M)) ，实际上又是 O(N log N + M log M) ，你仍然需要一个顺序比较器)，否则 std::unordered_set在 C++11 中(在这种情况下，预期时间为 O(N + M) 且出现病态的最坏情况，您需要专门化 std::hash 或以其他方式编写散列函数并提供等于函数，而不是顺序比较器)。在 C++11 之前，其他散列容器可用，只是标准中没有。

如果您不介意额外的内存并且不介意丢失原始顺序:

container<MyClass> items(first_array, first_array + N);
items.insert(second_array, second_array + M);
std::copy(items.begin(), items.end(), first_array);

如果您不想使用(很多)额外内存并且在源数组中有空间用于 M 个附加元素，而不是仅仅为结果留出空间:

std::copy(second_array, second_array + M, first_array + N);
std::sort(first_array, first_array + N + M);
MyClass *dst = std::unique(first_array, first_array + N + M);
// result now has (dst - first_array) elements