Самый длинный подрамник, элементы которого образуют непрерывную последовательность

Ответ 1

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

Вход: [a1, a2, a3,...]

Отобразить исходный массив как пару, где 1-й элемент - это значение, а 2nd - индекс массива.

Массив: [[a1, i1], [a2, i2], [a3, i3],...]

Сортируйте этот массив пар с некоторым алгоритмом O (n) (например, Counting Sort) для целочисленной сортировки по значению. Мы получаем еще один массив:

Массив: [[a3, i3], [a2, i2], [a1, i1],...]

где a3, a2, a1,... находятся в отсортированном порядке.

Запустить цикл через отсортированный массив пар

В линейном времени мы можем обнаружить последовательные группы чисел a3, a2, a1. Последовательное определение группы следующее value = prev значение + 1. Во время этого сканирования сохраняйте текущий размер группы (n), минимальное значение индекса ( min) и текущая сумма индексов ( actualSum).

На каждом шаге внутри последовательной группы мы можем оценить сумму индексов, поскольку они создают арифметическую прогрессию с первым элементом min, шагом 1 и размером группы, видимой до сих пор п. Эту оценку суммы можно сделать в O (1) раз, используя формулу для арифметической прогрессии:

оценка sum = (a1 + an) * n/2;

оценка sum = (min + min + (n - 1)) * n/2;

оценка sum = min * n + n * (n - 1)/2;

Если на каком-либо шаге цикла внутри последовательной групповой оценки сумма равна фактической сумме, то наблюдаемая до сих пор последовательная группа удовлетворяет условиям. Сохраните n как текущий максимальный результат или выберите максимум между текущим максимумом и n.

Если на элементах значения мы перестаем видеть последовательную группу, тогда reset все значения и делаем то же самое.

Пример кода: https://gist.github.com/mishadoff/5371821

Ответ 2

UPD2:. Следующее решение для проблемы, когда не требуется, чтобы подмассив был смежным. Я неправильно понял постановку проблемы. Не удаляя это, так как у кого-то может быть идея, основанная на моей, которая будет работать для реальной проблемы.

Вот что я придумал:

Создайте экземпляр словаря (который реализуется как хеш-таблица, давая O (1) в обычных ситуациях). Ключи представляют собой целые числа, значения - хэш-множества целых чисел (также O (1)) - var D = new Dictionary<int, HashSet<int>>.

Итерации через массив A и для каждого целого n с индексом i do:

• Проверьте, содержатся ли ключи n-1 и n+1 в D.
  • Если ни один из ключей не существует, выполните D.Add(n, new HashSet<int>)
  • если существует только один из ключей, например. n-1, do D.Add(n, D[n-1])
  • Если оба ключа существуют, выполните D[n-1].UnionWith(D[n+1]); D[n+1] = D[n] = D[n-1];
• D[n].Add(n)

Теперь пройдите через каждую клавишу в D и найдите хэш-набор с наибольшей длиной (длина поиска - O (1)). Наибольшая длина будет ответом.

Насколько я понимаю, наихудшей сложностью будет O (n * log (n)), только из-за операции UnionWith. Я не знаю, как вычислить среднюю сложность, но она должна быть близка к O (n). Пожалуйста, поправьте меня, если я ошибаюсь.

UPD: Говорить код, здесь тестовая реализация на С#, которая дает правильный результат в обоих примерах OP:

var A = new int[] {4, 5, 1, 5, 7, 6, 8, 4, 1};
var D = new Dictionary<int, HashSet<int>>();

foreach(int n in A)
{
    if(D.ContainsKey(n-1) && D.ContainsKey(n+1))
    {
        D[n-1].UnionWith(D[n+1]);
        D[n+1] = D[n] = D[n-1];
    }
    else if(D.ContainsKey(n-1))
    {
        D[n] = D[n-1];
    }
    else if(D.ContainsKey(n+1))
    {
        D[n] = D[n+1];
    }
    else if(!D.ContainsKey(n))
    {
        D.Add(n, new HashSet<int>());
    }

    D[n].Add(n);
}

int result = int.MinValue;
foreach(HashSet<int> H in D.Values)
{
    if(H.Count > result)
    {
        result = H.Count;
    }
}

Console.WriteLine(result);

Ответ 3

См. массив S в этом определении математического набора:

S = U _{j = 0} ^k (I _j)

Где я _j - непересекающиеся целые сегменты. Вы можете создать определенное дерево интервалов (на основе дерева Red-Black или дерева самобалансировки, которое вам нравится:)) для хранения массива в этих математических определениях. Структуры node и дерева должны выглядеть так:

struct node {
    int d, u;
    int count;
    struct node *n_left, *n_right;
}

Здесь d - меньшая граница целочисленного отрезка, а u - верхняя граница. count добавляется, чтобы учесть возможные дубликаты в массиве: при попытке вставить уже существующий элемент в дерево вместо того, чтобы ничего не делать, мы увеличим значение count node, в котором оно найдено.

struct root {
    struct node *root;
}        

Дерево будет хранить только узлы disjoint, поэтому вставка немного сложнее классической вставки красного-черного дерева. При вставке интервалов вы должны сканировать потенциальные переполнения с уже существующими интервалами. В вашем случае, поскольку вы будете вставлять только одноточие, это не должно слишком много накладывать лишние накладные расходы.

Учитывая три узла P, L и R, L - левый ребенок из P и R - правый ребенок P. Затем вы должны обеспечить выполнение L.u < P.d и P.u < R.d(и для каждого node, d <= u, конечно).

При вставке целочисленного сегмента [x, y] вы должны найти "перекрывающиеся" сегменты, то есть интервалы [u, d], которые удовлетворяют одному из следующих неравенств:

y >= d - 1
ИЛИ
x <= u + 1

Если вставленный интервал является singleton x, вы можете найти только до двух перекрывающихся интервальных узлов N1 и N2, таких как N1.d == x + 1 и N2.u == x - 1. Затем вам необходимо объединить два интервала и количество обновлений, что оставляет вас с N3 таким, что N3.d = N2.d, N3.u = N1.u и N3.count = N1.count + N2.count + 1. Поскольку дельта между N1.d и N2.u является минимальной дельта для двух сегментов, которые должны быть непересекающимися, то вы должны иметь одно из следующих значений:

• N1 - правильный дочерний элемент N2
• N2 - левый дочерний элемент N1

Таким образом, в худшем случае вставка будет < <212 > .

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

Ответ 4

Для этого потребуется два прохода над данными. Сначала создайте хэш-карту, сопоставив ints с bools. Я обновил свой алгоритм, чтобы не использовать карту, из STL, в которой я уверен, использует сортировку внутри. Этот алгоритм использует хеширование и может быть легко обновлен для любой максимальной или минимальной комбинации, даже потенциально все возможные значения, которые может получить целое число.

#include <iostream>

using namespace std;
const int MINIMUM = 0;
const int MAXIMUM = 100;
const unsigned int ARRAY_SIZE = MAXIMUM - MINIMUM;

int main() {

bool* hashOfIntegers = new bool[ARRAY_SIZE];
//const int someArrayOfIntegers[] = {10, 9, 8, 6, 5, 3, 1, 4, 2, 8, 7};
//const int someArrayOfIntegers[] = {10, 6, 5, 3, 1, 4, 2, 8, 7};
const int someArrayOfIntegers[] = {-2, -3, 8, 6, 12, 14,  4, 0, 16, 18, 20};
const int SIZE_OF_ARRAY = 11;

//Initialize hashOfIntegers values to false, probably unnecessary but good practice.
for(unsigned int i = 0; i < ARRAY_SIZE; i++) {
    hashOfIntegers[i] = false;
}

//Chage appropriate values to true.
for(int i = 0; i < SIZE_OF_ARRAY; i++) {
    //We subtract the MINIMUM value to normalize the MINIMUM value to a zero index for negative numbers.
    hashOfIntegers[someArrayOfIntegers[i] - MINIMUM] = true;
}

int sequence = 0;
int maxSequence = 0;
//Find the maximum sequence in the values
for(unsigned int i = 0; i < ARRAY_SIZE; i++) {

    if(hashOfIntegers[i]) sequence++;
    else sequence = 0;

    if(sequence > maxSequence) maxSequence = sequence;
}

cout << "MAX SEQUENCE: " << maxSequence << endl;
return 0;
}

Основная идея состоит в том, чтобы использовать хэш-карту как сортировку в виде ведра, так что вам нужно сделать только два прохода над данными. Этот алгоритм O (2n), который, в свою очередь, O (n)

Ответ 5

Не надейтесь, это всего лишь частичный ответ.

Я уверен, что проблема не разрешима в O(n). К сожалению, я не могу это доказать.

Если существует способ решить его менее чем за O(n^2), я бы предположил, что решение основано на следующей стратегии:

• Решите в O(n) (или, может быть, O(n log n)), существует ли непрерывная субарма, как вы ее описываете, по крайней мере, с элементами i. Позволяет называть этот предикат E(i).
• Используйте bisection, чтобы найти максимум i, для которого выполняется E(i).

Общее время работы этого алгоритма будет O(n log n) (или O(n log^2 n)).

Это единственный способ, с помощью которого можно было бы свести проблему к другой проблеме, которая, по крайней мере, может быть проще, чем исходная формулировка. Тем не менее, я не смог найти способ вычисления E(i) менее чем за O(n^2), поэтому я могу быть полностью отключен...

Ответ 6

вот еще один способ подумать о вашей проблеме: предположим, что у вас есть массив, состоящий только из 1s и 0s, вы хотите найти самый длинный последовательный запуск 1s. это можно сделать в линейном времени по длине кодирования 1s (игнорировать 0). чтобы преобразовать исходную проблему в эту новую проблему с кодировкой длины пробега, вы вычисляете новый массив b [i] = (a [i] < a [i + 1]). это не нужно делать явно, вы можете просто сделать это неявно для достижения алгоритма с постоянной потребностью в памяти и линейной сложностью.

Ответ 7

Вот 3 приемлемых решения:

Первое - это O(nlog(n)) во времени и O(n) пробел, второе - O(n) во времени и O(n) в пространстве, а третья - O(n) во времени и O(1) в пространстве.

• постройте a binary search tree, затем выполните в порядке.
  держите 2 указателя один для начала максимального подмножества и один для конца. сохраняйте значение max_size во время итерации дерева. это O(n*log(n)) сложность времени и пространства.

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

• Предполагая, что нет переполнения или большого целочисленного типа данных. Предполагая, что массив является математическим множеством (нет повторяющихся значений). Вы можете сделать это в O(1) памяти:

  • вычислить сумму массива и произведение массива
  • выяснить, какие цифры у вас есть, если у вас есть минимальный и максимальный исходный набор. В целом это временная сложность O(n).