Найти самую длинную серию единиц в двоичном массиве

Question

Как бы найти самую длинную серию единиц в этом массиве двоичных цифр - 100011101100111110011100

В этом случае ответ должен быть = 11111

Я думал о циклическом просмотре массива ипроверяя каждую цифру, если эта цифра равна единице, добавьте ее к новой строке, если ее ноль, то заново создайте новую строку, но сохраните ранее созданную строку.Когда закончите, проверьте длину каждой строки, чтобы увидеть, какая из них самая длинная.Я уверен, что есть более простое решение?

Answer 1

Ваш алгоритм хорош, но вам не нужно сохранять все временные строки - они все равно являются "единицами".

Вы должны просто иметь две переменные "bestStartPosition" и "bestLength".После того, как вы нашли последовательность «единицы» - вы сравниваете длину этой последовательности с сохраненным значением «bestLength» и перезаписываете обе переменные с новой позицией и длиной.

После того как вы отсканировали весь массив - у вас будет позициясамой длинной последовательности (если она вам нужна) и длины (по которой вы можете сгенерировать строку из «единиц»).

Answer 2

Обновление Java 8 с O (n) сложностью по времени (и только 1 строкой):

int maxLength = Arrays.stream(bitStr.split("0+"))
  .mapToInt(String::length)
  .max().orElse(0);

См. живая демонстрация .

Это также автоматически обрабатывает пустой ввод, возвращая 0 в этом случае.

---

Java 7 компактное решение, но O (n log n) сложность времени:

Пусть API Java сделает всю работу за вас всего за 3 строки:

String bits = "100011101100111110011100";

LinkedList<String> list = new LinkedList<String>(Arrays.asList(bits.split("0+")));
Collections.sort(list);
int maxLength = list.getLast().length(); // 5 for the example given

Как это работает:

1. bits.split("0+") разбивает входные данные на String[] с каждой непрерывной цепочкой из 1 (разделенных всеми нулями - регулярное выражение для этого 0+) становится элементом массива
2. Arrays.asList() превращает String[] в List<String>
3. Создание и заполнение нового LinkedList из только что созданного списка
4. Использование коллекций для сортировки списка.Самая длинная цепочка из 1 будет сортироваться последней
5. Получить длину последнего элемента (самого длинного) в списке.Вот почему был выбран LinkedList - у него есть метод getLast(), который, как мне показалось, был удобен

Для тех, кто считает, что это "слишком тяжело", с учетом входных данных образцаНа моем MacBook Pro потребовалось менее 1 мс.Если длина входной строки не превышает гигабайт, этот код будет выполняться очень быстро.

EDITED

Предложенный Максом использование Arrays.sort() очень похоже и выполняется в два раза быстрее, но все равно требует 3строки:

String[] split = bits.split("0+");
Arrays.sort(split);
int maxLength = split[split.length - 1].length();

Answer 3

Вот какой-то псевдокод, который должен делать то, что вы хотите:

count = 0
longestCount = 0
foreach digit in binaryDigitArray:
   if (digit == 1) count++
   else:
      longestCount = max(count, maxCount)
      count = 0
longestCount = max(count, maxCount)

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

Answer 4

У вас есть код предварительного просмотра только для php, возможно, вы сможете переписать его на свой язык.

Что скажет, какова максимальная длина единиц:

$match = preg_split("/0+/", "100011101100111110011100", -1, PREG_SPLIT_NO_EMPTY);
echo max(array_map('strlen', $match));

Результат:

 5