• Kак сортировать стрoку, которая содержит 0 и 1?

    @dvva Автор вопроса
    Start by having a counter that keeps track of how many adjacent 1's you have at the back of the string.
    Ie, 00110101111 => adjacent 1's = 4.

    Try to find a pair that is 11. Swap that in front of the adjacent 1's and increment the counter by 2.
    Ie, 100110101111 => 100100111111. Do this until there are non remaining.

    Try to find a pair that is 01. Swap that in front of the adjacent 1's and increment the counter by 1. If the 01 is one character away from the adjacent 1's, you'll need to swap it forwards first.
    Ie, 100010111111 => 101000111111 => 100001111111. Do this until there are non remaining.

    If the string starts with a 10, swap it backwards, and move the resulting 01 in front of the adjacent 1's and increment the counter by 1. Ie, 100001111111 => 001001111111 => 000011111111.

    This run's in O(n^2) operations average I beleive. I think there exists an algorithm that runs in O(n) operations however.
    Ответ написан
    1 комментарий