你如何找到数组中最长的不同(!)元素行?
我们有一个矩阵 我们的任务是在这个矩阵中找到一行,其中最长的一行是不同的元素
例如 0 1 2 3 4 1 2 3 应该计数 0 1 2 3 4 = 5 个元素
你如何找到数组中最长的不同(!)元素行?
我们有一个矩阵 我们的任务是在这个矩阵中找到一行,其中最长的一行是不同的元素
例如 0 1 2 3 4 1 2 3 应该计数 0 1 2 3 4 = 5 个元素
尝试使用此处描述的 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
假设您使用两种数据结构:
一个std::list
整数
将std::unordered_map
整数映射到列表的迭代器
现在操作如下。当遇到下一个整数时,检查它是否在无序映射中。
如果是,则在列表中找到相应的迭代器,并删除它以及它剩下的所有项目(来自列表和无序映射)
如果不是,则将其添加到列表中,并将无序地图设置为指向它
此外,在每个步骤中,跟踪步骤索引和无序映射(或列表)的大小。最后输出最大尺寸的索引。
该算法是摊销预期线性时间:尽管可能有一个步骤会删除多个列表项(从每个数据结构中),但每个项最多进入和离开一次。
例子
这是在某个步骤中的两个数据结构的示例。灰色地图引用蓝色链表中的项目。
不同的长度现在是 4。但是,如果现在遇到 2,那么它和它左侧的链接(在本例中为 3)将在添加之前被清除,并且长度将减少到 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
这不是非常优雅的解决方案,但它有效
您可以使用 Caterpillar 算法在 O(n) 中执行此操作。