arrays - 组合数组中的连续位

Question

我正在尝试组合给定数组中的连续相似位。示例:

输入:

a=[0 0 0 1 1 1 0 0 1 0];

输出:

b=[0 1 0 1 0];

我的输入数组大小超过 100000，所以显然我不想遍历我的整个输入数组。有没有更简单的方法？也许是递归的分而治之算法？仅供引用，我在 MATLAB 中运行它，所以任何使用矩阵运算的方法都很棒

Answer 1

循环遍历整个数组(至少在最坏的情况下)是最好不过的了。

这个解决方案当然是微不足道的 - 您只需循环 - 如果当前元素与最后一个元素不同，则将其添加到输出中。

---

您可以做得稍微比简单地增加一些复杂性的循环更好。

考虑一下当我们有以下情况时会发生什么:

...0x1... or ...1x0...

其中 x 是 0 或 1。 x 是什么并不重要，输出仍然是相同的。

因此，我们可以做的是检查每个第二个元素。如果该元素与后面位置 2 的元素不同，我们可以简单地将其添加到输出中并继续。如果相同，我们需要检查前一个元素(如果前一个元素不同，则将前一个和当前元素都添加到输出中，如果相同，则继续)。

---

请注意，循环 100000 个元素不会花费特别长的时间。