Найдите самую длинную последовательную последовательность различных элементов в последовательности

Question

Найдите самую длинную последовательную последовательность различных элементов в последовательности

Как найти самый длинный ряд различных (!) Элементов в массиве?

У нас есть матрица
Наша задача — найти в этой матрице строку, в которой находится самый длинный ряд различных элементов.

Например
0 1 2 3 4 1 2 3
Должен считать 0 1 2 3 4 = 5 элементов

2

algorithm c++data-stream data-structures

Решение

Другие решения

Предположим, вы используете две структуры данных:

std::list целых чисел
std::unordered_map отображение целых чисел в итераторы списка

Теперь действуйте следующим образом. Когда вы встретите следующее целое число, проверьте, находится ли оно в неупорядоченной карте.

Если это так, найдите соответствующий итератор в списке и удалите его и все оставшиеся элементы (из списка и неупорядоченной карты)
Если это не так, добавьте его в список и установите неупорядоченную карту, чтобы указать на него

Кроме того, на каждом шаге отслеживайте как индекс шага, так и размер неупорядоченной карты (или списка). Выведите индекс наибольшего размера в конце.

Этот алгоритм амортизированный ожидаемое линейное время: хотя может быть шаг, который удаляет более одного элемента списка (из каждой структуры данных), каждый элемент входит и покидает их не более одного раза.

пример

Вот пример двух структур данных на каком-то этапе. Серая карта ссылается на элементы в синем связанном списке.

Различная длина теперь равна 4. Однако, если теперь встречается 2, то он и ссылка (и), оставленные от него (в данном случае 3), будут удалены перед добавлением, а длина будет уменьшена до 3.

1

Вы можете сделать это в O (n), используя алгоритм гусеницы.

Указатели головы и хвоста начинаются в одном и том же месте. Вы перемещаете голову и добавляете к хэш-набору, если его там еще нет.
Если голова не может двигаться, двигайте хвостом. Удалите соответствующий номер из набора хэшей.
Пока вы идете, посмотрите, есть ли новая максимальная длина.
Голова и хвост находятся в каждом месте по одному разу, так что это O (n)

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

Это не очень элегантное решение, но оно работает

0

Источник

Accepted Answer

Попробуйте использовать алгоритм Кадане, описанный здесь: Максимальная проблема подмассива

Просто замените операцию суммирования операциями добавления в набор и поиска в наборе. Таким образом, вы можете создать 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

5