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

Ответ 1

Обновление.

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

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

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

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

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

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

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

• Постройте массив A с накопленным числом 1s от начала до этой позиции, например. если битстрона равна "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]), то есть она действительна, если ее длина удваивает количество единиц в ней. Например, подпоследовательность (3,6) справедлива, так как 6 - 3 + 1 == 2 * A [6] - A [2] = 4.

• Обычная старая двойная петля:

  maxSubsLength = 0 для я = 1 до N - 1 для j = я + 1 до N   if isValid (i, j)... #maintain maxSubsLength конец конец

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

Ответ 2

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

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

Ответ 3

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

Переходя от первой позиции битового массива, мы помещаем позицию в массив, начиная с середины массива (index is 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

Ответ 4

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

Ответ 5

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

Ответ 6

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

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

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

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

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

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

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

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

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

Ответ 8

Новое решение: Пространственная сложность 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;
            }
        }

Ответ 9

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

Если это о 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).