建议一个合适的算法来合并包含类对象的两个数组(没有重复)

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:或者编写比较器函数并将其提供给sort和set_union.

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

如果first_array或者second_array可能已经包含dupes(不仅仅是它们之间),那么你需要一个额外的步骤来删除它们,这不仅会丢失顺序而且会丢失源数组中的dupes:

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;
    }
}

如果数组本身可以包含dupes,那么从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