Выведите n-й проход для этой последовательности строк

Question

У вас есть строка, состоящая из символов «0» и «1». Рассмотрим последовательность '01011010'. Поменяйте местами 0 и 1, если за 0 следует 1. Выведите n-й проход последовательности.

• Пропуск 1: «10101100»
• Пропуск 2: '11010100'
• Пропуск 3: «11101000»
• Пропуск 4: '11110000'

Кажется, это модифицированная пузырьковая сортировка, где нам нужно вывести n-й проход. Мой алгоритм:

while (pass != 0)
    begin
        bool x = false;
        int prev = ∞;
        for (int i = 0; i < string_length; i++)
        begin
            if (prev == 0) then
                switch (string[i])
                    case 0:
                        break;
                    case 1:
                        string[i] = 0;
                        string[i-1] = 1;
                        prev = ∞;
                        x = true;
                        break;
            else
                prev = string[i];
            end if
        end
        if (!x) 
            break;
        pass = pass - 1;

    end

Вывод правильный, но алгоритм не такой эффективный. Худший случай - все еще O (n ^ 2). Может ли кто-нибудь помочь мне уменьшить сложность времени?

Спасибо!

Answer 1

Вот возможный путь вперед. Я понимаю, что это постоянный конкурс .

Рассмотрим период «ожидания» каждого 1. Мы имеем дело с единицами, у которых другие 1 находятся непосредственно слева от них, и им приходится «ждать», прежде чем они смогут начать движение; а также с единицами, у которых недостаточно нулей, чтобы предотвратить дополнительные «ожидания», когда они достигают других групп единиц.

Пример:

        "waiting" periods
        0 1 2 3     0+3-2+1
        ^ ^ ^ ^     ^ 1+3-2+1
        ^ ^ ^ ^     ^ ^
0 0 0 0 1 1 1 1 0 0 1 1
0 0 0 1 0 1 1 1 0 1 0 1
0 0 1 0 1 0 1 1 1 0 1 0
0 1 0 1 0 1 0 1 1 1 0 0
1 0 1 0 1 0 1 0 1 1 0 0
1 1 0 1 0 1 0 1 0 1 0 0
              ^   ^
              ^   5 moves - 3 wait
              ^
              5 moves - 2 wait

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