4

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

4

2 回答 2

6

前提是您不介意丢失两个数组的原始顺序：

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化：或者编写一个比较器函数并将其提供给sortand 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空 and开头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
于 2012-10-10T09:29:22.423 回答
3

使用 x、y、z 对对象进行比较，对两个数组（或副本，如有必要）进行排序，然后创建一个辅助目标列表，将第一个中的所有元素复制到其中，并且仅将第二个中的不匹配元素复制到该列表中。如有必要，复制回第一个数组。

复杂性：max(O(n log n),O(m log m))，因为排序占主导地位，并且填充目标列表在 O(max(n,m)) 上。

这并不是说该算法一定是有效的：对于较小的数组，复制和排序将占主导地位。

于 2012-10-10T09:29:58.237 回答