组重复在向量项 - C++

Question

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

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

Answer 1

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

..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，我们需要再检查一次（不是真的） - 如果群集是空的，这意味着最后一个元素不是它的一部分，而是一个新元素。否则，最后一个集群尚未添加，您需要将最后一个元素添加到它，然后添加集群。我要把这个留给你。

Answer 2

您应该使用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; 
}