c++ - 查找序列中不同项目的最长连续子序列

Question

你如何找到数组中最长的不同（！）元素行？

我们有一个矩阵 我们的任务是在这个矩阵中找到一行，其中最长的一行是不同的元素

例如 0 1 2 3 4 1 2 3 应该计数 0 1 2 3 4 = 5 个元素

Answer 1

尝试使用此处描述的 Kadane 算法：Maximum Subarray Problem

只需将 sum 操作替换为 add-to-set 和 find-in-set 操作。因此，您可以创建一个 O(n) 算法。

这是我的尝试：

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    int mas[] = {1,2,3,1,2,3,4,1,2};
    size_t count = sizeof(mas)/sizeof(mas[0]);

    size_t best = 0;
    int best_index = 0;
    unordered_set<int> unique;
    for (int i = 0; i < count; i++) {
        while (unique.find(mas[i]) != unique.end()) {
            unique.erase(mas[i - unique.size()]);
        }
        unique.insert(mas[i]);
        if (unique.size() > best) {
            best = unique.size();
            best_index = i - best + 1;
        }
    }

    cout << "Index = " << best_index << " Length = " << best << endl;
}

给出输出：

Index = 3 Length = 4

Answer 2

假设您使用两种数据结构：

• 一个std::list整数

• 将std::unordered_map整数映射到列表的迭代器

现在操作如下。当遇到下一个整数时，检查它是否在无序映射中。

• 如果是，则在列表中找到相应的迭代器，并删除它以及它剩下的所有项目（来自列表和无序映射）

• 如果不是，则将其添加到列表中，并将无序地图设置为指向它

此外，在每个步骤中，跟踪步骤索引和无序映射（或列表）的大小。最后输出最大尺寸的索引。

该算法是摊销预期线性时间：尽管可能有一个步骤会删除多个列表项（从每个数据结构中），但每个项最多进入和离开一次。

---

例子

这是在某个步骤中的两个数据结构的示例。灰色地图引用蓝色链表中的项目。

不同的长度现在是 4。但是，如果现在遇到 2，那么它和它左侧的链接（在本例中为 3）将在添加之前被清除，并且长度将减少到 3。

Answer 3

尝试这样的事情：

  const int len = 4;
  int arr[len][len] = {{1, 2, 2, 2}, {3, 2, 3, 5}, {2, 4, 3, 6}, {1, 1, 1, 1}};
  int max = -1, current = 1;
  for (int i = 0; i < len; i++) {
    for (int j = 1; j < len; j++) {
      if (arr[i][j] != arr[i][j - 1]) {
        current++;
      } else {
        if (current > max) {
          max = current;
        }
        current = 1;
      }
    }
    if (current > max) {
      max = current;
    }
    current = 1;
  }
  // output max      

这不是非常优雅的解决方案，但它有效

Answer 4

您可以使用 Caterpillar 算法在 O(n) 中执行此操作。

• 头和尾指针从同一位置开始。如果它不存在，则移动头部并添加到哈希集中。
• 如果头不能动，就动尾巴。从哈希集中删除相应的数字。
• 随着您的进行，请查看是否有新的最大长度。
• 头部和尾部在每个位置都各有一次，所以它是 O(n)