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

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

Учитывая несортированный массив положительных целых чисел, найдите длину самого длинного подмассива, элементы которого при сортировке непрерывны. Можете ли вы придумать решение O (n)?

Пример:

{10, 5, 3, 1, 4, 2, 8, 7}, ответ 5.

{4, 5, 1, 5, 7, 6, 8, 4, 1}, ответ 5.

В первом примере подматрица {5, 3, 1, 4, 2} при сортировке может образовывать непрерывную последовательность 1,2,3,4,5, которые являются самыми длинными.

Для второго примера подматрица {5, 7, 6, 8, 4} является субаром результата.

Я могу думать о методе, который для каждого подмассива, проверяет, равен ли (максимум - минимум + 1) длину этого подмассива, если это правда, то это непрерывный подмассива. Возьмите самый длинный из всех. Но это O (n ^ 2) и не может иметь дело с дубликатами.

Может ли кто-нибудь дать лучший метод?

4b9b3361

ОТВЕТЫ

Ответ 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).