我有一个数组,其中每个位置都包含一个具有三个 int 值 (x,y,z) 的类对象。现在必须从不同的数组中将所有元素复制到源数组中。对于每个数组元素,我们需要检查 x、y、z 值以避免重复。有没有可能比 o(n^2) 更有效?
最佳答案
前提是你不介意丢失两个数组原来的顺序:
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
关于c++ - 建议一个合适的算法来合并两个包含类对象的数组(不重复),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12816043/