使用c ++中的公共/重复元素对向量进行分组和排序

Question

假设我有一个向量如下

std::vector<int> v = {3, 9, 7, 7, 2};

我想对这个元素向量进行排序,以便将向量存储为77932.首先,我们存储公共元素(7),然后我们将剩余元素从最高到最低排序.

如果我有一个矢量如下

std::vector<int> v = {3, 7, 7, 7, 2};

在这里,它将导致77732.

同样的

std::vector<int> v = {7, 9, 2, 7, 9};

它应该导致99772,因为9s高于7s.

最后一个例子

std::vector<int> v = {7, 9, 7, 7, 9};

它应该导致77799,因为有7s而不是9s.

什么是最快的算法来实现这个？

Answer 1

使用std::multiset为您做计数.然后使用排序与平局决胜逻辑简单的自定义比较具有实现的std::tie:

std::vector<int> data = {7, 9, 2, 7, 9};
std::multiset<int> count(data.begin(), data.end());
std::sort(
    data.begin()
,   data.end()
,   [&](int a, int b) {
        int ca = count.count(a);
        int cb = count.count(b);
        return std::tie(ca, a) > std::tie(cb, b);
    }
);
std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " "));

演示1

编辑: count(n)函数的std::multiset重复次数是线性的,这可能会降低排序算法的性能.您可以通过std::unordered_map在其位置使用来解决此问题:

std::vector<int> data = {7, 9, 2, 7, 9};
std::unordered_map<int,int> count;
for (auto v : data)
    count[v]++;
std::sort(
    data.begin()
,   data.end()
,   [&](int a, int b) {
        return std::tie(count[a], a) > std::tie(count[b], b);
    }
);
std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " "));

演示2.