string - 输出此字符串序列的第 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

这是一个可能的前进方向。我知道这是一个正在进行的 contest .

考虑每个 1 的“等待”期。我们关注的是在其左侧直接有其他 1 的 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 可能结束的地方。