3

你如何找到数组中最长的不同(!)元素行?

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

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

4

4 回答 4

6

尝试使用此处描述的 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
于 2016-03-29T22:08:29.913 回答
1

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

  • 一个std::list整数

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

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

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

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

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

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


例子

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

在此处输入图像描述

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

于 2016-03-29T22:21:41.843 回答
0

尝试这样的事情:

  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      

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

于 2016-03-29T22:22:11.633 回答
0

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

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