组重复在向量项 - C++

问题描述：

INPUT : [3,3,3,2,2,2,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0]组重复在向量项 - C++

OUTPUT : [[3,3,3],[2,2,2],[1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0]]

输入是为int的向量，而输出是整数的向量的向量。目标是以时间最有效的方式做到这一点。

我目前使用的解决方案是这样的：

vector<vector<int> results; 
vector<int> result; 

for(int i = 0 ; i < list.size() - 1 ; i++){ 
    result.push_back(list[i]); 
    if (list[i] != list[i+1]){ 
     results.push_back(result); 
     result.clear(); 
    } 
} 

result.push_back(list[list.size()-1]); 
results.push_back(result);

信贷：@kabanus

欢迎stackoverflow.com。请花些时间阅读[帮助页面]（http://stackoverflow.com/help），尤其是名为[“我可以问些什么话题？”]的章节（http://stackoverflow.com/help/）讨论话题）和[“我应该避免问什么类型的问题？”]（http://stackoverflow.com/help/dont-ask）。还请[参观]（http://stackoverflow.com/tour）和[阅读如何提出好问题]（http://stackoverflow.com/help/how-to-ask）。最后，请学习如何创建[最小，完整和可验证示例]（http://stackoverflow.com/help/mcve）。 –

任何简单的工作算法都可能足够接近最高效。 – aschepler

如果你没有任何东西，最有效的就是任何有效的东西。写一些有用的东西，然后才开始考虑效率。 – user463035818

答

你靠近。你已经想通了你的边界问题，但考虑在集群的接口会发生什么：

..2,2,3,3... 
    ^^ 
    i i+1

你要进入else（else if是不必要的，如果条件是原if正好相反），而忘记最后加上2。如果在向量中没有重复项，例如

`{1,2,3,4}`

您不会添加除空集群以外的任何内容！所以，你总是想添加数字，而不是你在一个集群中或结束它。如果您要结束集群，您还需要将其添加并清除。

for(int i = 0 ; i < sorted.size()-1 ; i++){ 
    cluster.push_back(sorted[i]); 
    if (sorted[i] != sorted[i+1]){ 
     clusters.push_back(cluster); 
     cluster.clear(); 
    } 
}

最后，由于@ tobi303提到最后一个元素缺失。使用单个元素的列表（{3}）尤其明显。请注意，最后一个群集在任何情况下都不会添加，无论它是最后一个新的单个元素还是最后一个群集。

所以，一旦我们退出for，我们需要再检查一次（不是真的） - 如果群集是空的，这意味着最后一个元素不是它的一部分，而是一个新元素。否则，最后一个集群尚未添加，您需要将最后一个元素添加到它，然后添加集群。我要把这个留给你。

你的代码仍然有一个出界的访问.... – user463035818

@ tobi303不，它不:)谢谢，我只是复制粘贴。 – kabanus

...现在你想念最后一个元素 – user463035818

答

您应该使用standard algorithm library尽可能

这是一个可能的实现：

template <class T> 
auto make_clusters(std::vector<T>& v) -> std::vector<std::vector<T>> 
{ 
    std::vector<std::vector<T>> clusters; 

    auto cluster_begin = v.begin(); 
    while (cluster_begin != v.end()) 
    { 
     auto elem = *cluster_begin; 

     auto cluster_end = std::find_if(cluster_begin, v.end(), 
             [&](int e) { return e != elem; }); 
     clusters.emplace_back(std::distance(cluster_begin, cluster_end), elem); 

     cluster_begin = cluster_end; 
    } 

    return clusters; 
}

感谢bolov。你是否能够指出如何修改它，而不是使用int，它是一个struct.x结构，执行int的函数。 –

@MacAhmed完成。请参阅编辑 – bolov

组重复在向量项 - C++

相关推荐