如何在迭代数组时分组“不同”的元素（例如：{1,2,2,1,3,3,3,2,1,1} 到 {1, 2} {2, 1, 3} {3} {3, 2, 1} {1}）？

Question

我有一个数组

int a[]={1,2,2,1,3,3,3,2,1,1};

如果我想在迭代元素时将相同的元素分组（不使用任何临时变量或数组来存储或复制元素），例如，在迭代时打印相同的元素，则可以这样实现：

1 
2 2 
1 
3 3 3 
2 
1 1 

我可以像这样使用for循环和if条件语句：

#include <stdio.h>
int main(){
    int a[]={1,2,2,1,3,3,3,2,1,1};
    for(int i=0,j=0;i<sizeof(a)/sizeof(int);i++){
        if(i==sizeof(a)/sizeof(int)-1 || a[i]!=a[i+1]){
            for(;j<=i;j++){
                printf("%d ",a[j]);
            }
            printf("\n");
        }
    }
    return 0;
}

现在我想在迭代时对“不同”的元素进行分组：每个组附近没有相同的元素：

1 2 
2 1 3 
3 
3 2 1 
1 

是否有可能提供与以前版本类似的解决方案？

for(int i=0,j=0;i<sizeof(a)/sizeof(int);i++){
    if(...){
        for(;j<=i;j++){
            printf("%d ",a[j]);
        }
        printf("\n");
    }
}

能否迭代数组并打印出结果，而不需要使用任何临时变量？

- ggrr

---

如果一个元素与下一个元素相同，则打印 '\n'。在结束时要小心处理。（或者反过来，检查它是否与前一个元素相同，并在开始时要小心处理）。 - BoBTFish

@amuse 如果您不想使用任何临时变量，请看我的解决方案。 - Sumeet

@TimBiegeleisen http://meta.stackoverflow.com/questions/322319/what-can-be-done-to-encourage-community-involvement - Jonathan Mee

Answer 1

int a[] = {1,2,2,1,3,3,3,2,1,1};

int prev = a[0];
bool first = false;
printf("%d", prev);

for (int i=1; i < sizeof(a) / sizeof(int); ++i) {
    int curr = a[i];
    if (curr != prev) {
        // start a new line for a new group
        printf("\n");
        first = true;
    }
    if (!first) {
        // print a space after each element
        printf(" ");
    }
    printf("%d", curr);
    first = false;
    prev = curr;
}

- Tim Biegeleisen

---

int first：我更愿意在C++中使用bool。 - Melebius

根据使用 printf，并且没有看到任何一个 std::，我认为他把它误认为是一个关于 C 的问题。 - BoBTFish

@BoBTFish 我不是一个C++专业人士（从事职业），但这个问题对我很有趣，所以我尝试回答了一下。 - Tim Biegeleisen

Answer 2

问题可以很容易地在数组的一次迭代中解决，不需要使用任何临时变量。

主要思路是在打印当前索引处的元素之前先查看前面的元素，如果它们匹配，则必须将当前索引处的元素放置在新行上，就这样。

第一个元素被打印，循环从第二个元素开始，因为第一个元素没有任何元素在其后面。

使用这个基本思路，代码如下：

int a[] = {1,2,2,1,3,3,3,2,1,1};
//print the first element
printf("%d ",a[0]);
for (int i=1; i < sizeof(a) / sizeof(int); ++i) {
 //check if the element at current index matches previous element.
 if(a[i] == a[i-1]) 
  printf("\n%d ",arr[i]);
 else printf("%d ",arr[i]);

}

- Sumeet

---

我几乎喜欢这个，除了它总是在每一行上打印一个额外的空格（不是世界末日）。 - Tim Biegeleisen

@TimBiegeleisen 尝试将第一个格式说明符更改为 "%d"，然后在循环中将其他说明符更改为 "\n%d" 和 " %d" 或者使用 cout << a[0]; 然后 cout << '\n' << arr[i]; 和 cout << ' ' << arr[i];。然后我意识到你已经以这种方式回答了 ;) ... - Bob__

Answer 3

这个问题很适合用 adjacent_find 来解决。

如果要对不同的元素进行分组，可以这样做：

auto i = cbegin(a);

for (auto j = adjacent_find(cbegin(a), cend(a)); j != cend(a); i = j, j = adjacent_find(i, cend(a))) {
    copy(i, ++j, ostream_iterator<decltype(*cbegin(a))>(cout, " "));
    cout << endl;
}
copy(i, cend(a), ostream_iterator<decltype(*cbegin(a))>(cout, " "));

要对类似的元素进行分组，你可以简单地使用 not_equal_to 作为 adjacent_find 的二元谓词：

auto i = cbegin(a);

for (auto j = adjacent_find(cbegin(a), cend(a), not_equal_to<decltype(*cbegin(a))>()); j != cend(a); i = j, j = adjacent_find(i, cend(a), not_equal_to<decltype(*cbegin(a))>())) {
    copy(i, ++j, ostream_iterator<decltype(*cbegin(a))>(cout, " "));
    cout << endl;
}
copy(i, cend(a), ostream_iterator<decltype(*cbegin(a))>(cout, " "));

实时示例

注意：尽管decltype(*cbegin(a))可能看起来有点复杂，但它可以被替换为int，但是您将失去灵活性。现在，如果您希望任意声明a为string甚至set<double>，则此代码不需要更改。

- Jonathan Mee

Answer 4

无论你为解决这个问题所做的努力，其时间复杂度都是O(N^2)。但是有可能用时间复杂度为O(N)的方法来解决这个问题，前面的答案已经很好地解释了这一点。但我认为你只需要通过改变if(...)就可以解决这个问题。我在这里找到了一个解决方案。将该行代码替换为以下代码。

if( (i<sizeof(a)/sizeof(int) && a[i]==a[i+1]) || i==sizeof(a)/sizeof(int)-1 )

你不需要改变其他任何东西。

我认为(i<sizeof(a)/sizeof(int) && a[i]==a[i+1])部分非常容易理解，而i==sizeof(a)/sizeof(int)-1部分则是针对最后一个元素的，如果最后一个元素等于倒数第二个元素。

- biswas N