Нахождение максимальной подпоследовательности двоичных наборов, имеющих одинаковое число 1 и 0

Question

В интернете я обнаружил следующую проблему и хотел бы узнать, как мне ее решить:

Вам дан массив ', содержащий 0 и 1.Найти O (n) время и O (1) пространство алгоритм, чтобы найти максимальную подпоследовательность, которая имеет равное число 1 и 0.

Примеры:

1. 10101010 -Самая длинная подпоследовательность, которая удовлетворяет проблеме, - это сам вход
2. 1101000 - Самая длинная подпоследовательность, которая удовлетворяет проблеме: 110100

Answer 1

Обновление .

Я должен полностью перефразировать свой ответ.(Если вы проголосовали за более раннюю версию, ну, вы были обмануты!)

Давайте снова подведем итог простого случая, чтобы убрать его с пути:

Найдите самый длинный префикс битовой строки, содержащей равное количество единиц и нулей массива.

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

Теперь давайте переключимся на более сложную версию проблемы: нам больше не нужно, чтобы подпоследовательности были префиксами - они могут начинаться где угодно.

После некоторых размышлений я подумал, что для этого не может быть линейного алгоритма.Например, рассмотрим префикс "111111111111111111 ...".Каждый 1 из них может быть началом самой длинной подпоследовательности, нет никакой начальной позиции подпоследовательности-кандидата, которая доминирует (то есть всегда дает лучшие решения, чем) любой другой позиции, поэтому мы не можем выбросить ни одну из них (O (N)пробел) и на любом шаге мы должны иметь возможность выбрать лучший старт (который имеет равное число 1 с и 0 с текущей позицией) из линейно большого числа кандидатов за O (1) времени. Оказывается, это выполнимо , и также легко выполнимо, так как мы можем выбрать кандидата на основе текущей суммы 1 с (+1) и 0 с (-1), это имеет не более размера N, имы можем сохранить первую позицию, которую достигнем каждой суммы, в 2N ячейках - см. ответ pmod ниже (комментарии yellowfog и геометрическая проницательность).

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

• Построить массив A с накопленным числом 1 от начала до этой позиции, напримересли цепочка битов равна «001001001», то массив будет [0, 0, 1, 1, 1, 2, 2, 2, 3].Используя это, мы можем проверить в O (1), действительна ли подпоследовательность (i, j) включительно: isValid(i, j) = (j - i + 1 == 2 * (A[j] - A[i - 1]), то есть она действительна, если ее длина вдвое больше, чем 1 в ней.Например, подпоследовательность (3,6) действительна, потому что 6 - 3 + 1 == 2 * A [6] - A [2] = 4.

• Простой старый двойной цикл:

  maxSubsLength = 0 для i = 1 до N - 1 для j = i + 1 до N, если isValid (i, j) ... #maintain maxSubsLength end end

Это можно немного ускорить, используя некоторые ветвления и ограничения, пропуская i / j последовательности, которые короче текущего maxSubsLength, но асимптотически это все еще O (n ^ 2).Медленно, но с большим плюсом на боку: правильно!

Answer 2

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

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

Answer 3

Новое решение: Предположим, у нас есть для n-битного входного массива 2 * массив размера n, чтобы сохранить позицию бита.Таким образом, размер элемента массива должен иметь достаточный размер, чтобы сохранить максимальный номер позиции.Для 256 входных битовых массивов необходим массив байтов 256x2 (достаточно байта, чтобы сохранить 255 - максимальную позицию).

Переходя от первой позиции битового массива, мы помещаем позицию в массив, начиная с середины массива (индекс равен n), используя правило:

1.Увеличивайте позицию, если мы передали бит «1», и уменьшаем, когда передаем бит «0»

2.Когда встречаете уже инициализированный элемент массива - не меняйте его и запомните разницу между позициями (текущий минус взят из элемента массива) - это размер локальной максимальной последовательности.

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

Например: битовая последовательность 0,0,0,1,0,1

   initial array index is n
   set arr[n] = 0 (position)
     bit 0 -> index--
   set arr[n-1] = 1 
     bit 0 -> index--
   set arr[n-2] = 2
     bit 0 -> index--
   set arr[n-3] = 3
     bit 1 -> index++
   arr[n-2] already contains 2 -> thus, local max seq is [3,2] becomes abs. maximum
      will not overwrite arr[n-2]
     bit 0 -> index--
   arr[n-3] already contains 3 -> thus, local max seq is [4,3] is not abs. maximum
     bit 1 -> index++
   arr[n-2] already contains 2 -> thus, local max seq is [5,2] is abs. max

Таким образом, мы проходим весь массив битов только один раз.Это решает задачу?

input:
    n - number of bits
    a[n] - input bit-array

track_pos[2*n] = {0,};
ind = n;
/* start from position 1 since zero has
  meaning track_pos[x] is not initialized */
for (i = 1; i < n+1; i++) {
    if (track_pos[ind]) {
        seq_size = i - track_pos[ind];
        if (glob_seq_size < seq_size) {
            /* store as interm. result */
            glob_seq_size = seq_size;
            glob_pos_from = track_pos[ind];
            glob_pos_to   = i;
        }
    } else {
        track_pos[ind] = i;
    }

    if (a[i-1])
        ind++;
    else
        ind--;
}

output:
    glob_seq_size - length of maximum sequence
    glob_pos_from - start position of max sequence
    glob_pos_to   - end position of max sequence

Answer 4

В этой теме (http://discuss.techinterview.org/default.asp?interview.11.792102.31) автор А.Ф. дал алгоритм, который выполняется за O (n) времени и использует O (sqrt (n log n)) битов.

Answer 5

Я не уверен, является ли массив, на который вы ссылаетесь, массивом массива 0 и 1 или битовым массивом ??

Если речь идет о bitarray, вот мой подход:

int isEvenBitCount(int n)
{
    //n ... //Decimal equivalent of the input binary sequence
    int cnt1 = 0, cnt0 = 0;
    while(n){
        if(n&0x01) { printf("1 "); cnt1++;}
        else { printf("0 "); cnt0++; }
        n = n>>1;
    }
    printf("\n");
    return cnt0 == cnt1;
}

int main()
{
    int i = 40, j = 25, k = 35;

    isEvenBitCount(i)?printf("-->Yes\n"):printf("-->No\n");
    isEvenBitCount(j)?printf("-->Yes\n"):printf("-->No\n");
    isEvenBitCount(k)?printf("-->Yes\n"):printf("-->No\n");
}

с использованием побитовых операций сложность времени также почти равна O (1).

Answer 6

Новое решение: Пространственная сложность O (1) и временная сложность O (n ^ 2)

        int iStart = 0, iEnd = 0;
        int[] arrInput = { 1, 0, 1, 1, 1,0,0,1,0,1,0,0 };

        for (int i = 0; i < arrInput.Length; i++)
        {
            int iCurrEndIndex = i;
            int iSum = 0;
            for (int j = i; j < arrInput.Length; j++)
            {                    
                iSum = (arrInput[j] == 1) ? iSum+1 : iSum-1;
                if (iSum == 0)
                {
                    iCurrEndIndex = j;
                }

            }
            if ((iEnd - iStart) < (iCurrEndIndex - i))
            {
                iEnd = iCurrEndIndex;
                iStart = i;
            }
        }

Answer 7

Попробуйте что-то вроде этого:

/* bit(n) is a macro that returns the nth bit, 0 or 1. len is number of bits */
int c[2] = {0,0};
int d, i, a, b, p;
for(i=0; i<len; i++) c[bit(i)]++;
d = c[1] < c[0];
if (c[d] == 0) return; /* all bits identical; fail */
for(i=0; bit(i)!=d; i++);
a = b = i;
for(p=0; i<len; i++) {
  p += 2*bit(i)-1;
  if (!p) b = i;
}
if (a == b) { /* account for case where we need bits before the first d */
  b = len - 1;
  a -= abs(p);
}
printf("maximal subsequence consists of bits %d through %d\n", a, b);

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

Answer 8

Как указал пользователь "R ..", строго говоря, решения не существует, если вы не игнорируете сложность пространства "log n".Далее я буду считать, что длина массива вписывается в машинный регистр (например, 64-разрядное слово) и что машинный регистр имеет размер O (1).

Важно отметить, что еслиздесь больше 1, чем 0, то максимальная подпоследовательность, которую вы ищете, обязательно включает в себя все 0 и столько 1.Итак, вот алгоритм:

Обозначения: массив имеет длину n , индексы отсчитываются от 0 до n-1 .

1. Первый проход: подсчитайте количество 1 ( c1 ) и 0 ( c0 ).Если c1 = c0 , то ваша максимальная подпоследовательность - весь массив (конец алгоритма).В противном случае пусть d будет цифрой, которая появляется реже ( d = 0 , если c0 , в противном случае d = 1 ).
2. Вычислить m = min (c0, c1) * 2 .Это размер подпоследовательности, которую вы ищете.
3. Второй проход: отсканируйте массив, чтобы найти индекс j первого вхождения d .
4. Вычислить k = max (j, n - m) .Подпоследовательность начинается с индекса k и имеет длину m .

Обратите внимание, что может быть несколько решений (несколько подпоследовательностей максимальной длины, которые соответствуют критерию).

Проще говоря: если предположить, что больше 1, чем 0, то я рассмотрю наименьшую подпоследовательность, которая содержит все 0.По определению эта подпоследовательность окружена пучками 1.Поэтому я просто беру достаточно 1-х с боков.

Редактировать: , как было указано, это не работает ... "Важный момент" на самом деле неправильный.

Answer 9

перебор: начните с максимальной длины массива для подсчета o и l. если все равно, вы закончили. иначе уменьшите длину поиска на 1 и выполните алгоритм для всех подпоследовательностей уменьшенной длины (то есть максимальной длины минус уменьшенная длина) и так далее. остановка, когда вычитание равно 0.