基于对象元素合并相似的对象为o（n＆＃xb2;）。如何使其更简单？

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

想要改进此问题吗？更新该问题，因此它仅针对一个问题，仅编辑此帖子。

闭合 2年前。

Answer 1

如果您对输入进行排序，则可以在O（nlogn * mlogm）中执行此操作，然后进行线性通过以合并。

n是v的长度，m是a :: W s的长度。

bool compare(const A & lhs, const A & rhs) {
    return std::tie(lhs.x, lhs.y) < std::tie(rhs.x, rhs.y);
}

std::sort(v.begin(), v.end(), compare);
for (auto first = v.begin(), last = {}; it != v.end(); it = last) {
    A result = *first;
    last = std::upper_bound(first++, v.end(), result, compare);
    for (; first != last; ++first) {
        if (first->z) {
            result.z = first->z;
        }

        // this is an in-place set_union
        std::merge(result.w.begin(), result.w.end(), first->w.begin(), first->w.end());
        auto unique_end = std::unique(result.w.begin(), result.w.end());
        result.w.erase(unique_end, result.w.end());
    }
    merged.push_back(result);
}

Answer 2

最好的方法是使用std :: unordered_map这将允许在恒定时间内找到匹配项，因此最终的时间复杂性将为o（n）：

class A {
public:
    int x, y, z;
    std::vector<int> w;
};

struct Point2d {
    int x, y;

    Point2d(int x, int y)
        : x { x }
        , y { y }
    {
    }
    Point2d(const A& a)
        : x { a.x }
        , y { a.y }
    {
    }
};

bool operator==(const Point2d& l, const Point2d& r)
{
    return l.x == r.x && l.y == r.y;
}

template <>
struct std::hash<Point2d> {
    size_t operator()(const Point2d& p) const
    {
        std::hash<int> sub_hash {};
        return (sub_hash(p.x) * 16777619) ^ sub_hash(p.y);
    }
};

template <typename T, typename F>
std::unordered_map<Point2d, A> merge_collection(const T& collection, F f)
{
    std::unordered_map<Point2d, A> r;
    for (const auto& item : collection) {
        f(r[item], item);
    }

    return r;
}

void merge_a(A& dest, const A& toMerge)
{
    std::vector<int> w;
    w.reserve(dest.w.size() + toMerge.w.size());

    std::merge(dest.w.begin(), dest.w.end(), toMerge.w.begin(), toMerge.w.end(), std::back_inserter(w));
    dest = {dest.x, dest.y, dest.z, std::move(w)};
}

template <typename T>
std::unordered_map<Point2d, A> merge_collection(const T& collection)
{
    return merge_collection(collection, merge_a);
}

https://godbolt.org/z/wz8vbz4h1