Поиск последовательных чисел из арифметического ряда в массиве случайных чисел

Question

У меня был экзаменационный вопрос с просьбой найти решение, чтобы найти, сколько последовательных чисел в арифметических рядах n, n * 2, n * 3, n * i (где i - длина массива - 1) находятся в массиве случайных чисел , Числа из серии могут быть в любом порядке в массиве, если вы начинаете с n и числа являются последовательными. Повторы разрешены.

Например: n = 2 и ваш массив [4, 5, 1, 2, 1, 2, 6, 10]

вернул бы 3. Поскольку самый длинный последовательный прогон, начинающийся с 2, равен 2, 4, 6.

Решение, которое я предложил, состояло в том, чтобы преобразовать вышеуказанный массив в [2, 0, 0, 1, 0, 1, 3, 5] путем деления чисел, делимых на n (2) на n, и изменения чисел, которые не являются модулями n до 0.

Затем я быстро сортирую массив в [0, 0, 0, 1, 1, 2, 3, 5] и выполняю линейную проверку, чтобы найти ответ.

Это дает мне решение, которое равно 2n + n log n или O (n log n).

Есть ли лучшее решение этой проблемы? Я имею в виду на порядок лучше, как O (n).

Answer 1

Решением O (i) с использованием дополнительного пространства памяти было бы использование битового вектора размера i, инициализированного равным 0. Итерируйте по массиву и установите запись j в единицу, если вы встретите n * j. После этого найдите число единиц в начале битового вектора.

Answer 2

Вы начали хорошо.Прокрутите массив и установите для каждой ячейки массива Aj значение Aj / n .

Создайте битовый массив длины i-1 (выиметь i-1 номер).

Установите их все в нули.

Снова переберите массив, для каждого встречаемого числа ( k ) установите бит k (если этоменьше чем m ) до 1.

Проходить по битовому массиву с места 1 и останавливаться на первом нуле.Вот результат.

Вы получили около 4 * i Итераций ... O (i)

Answer 3

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