組重複在向量項 - 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; 
}