字符的左右移动的问题


给定一个字符串,这个字符串为 * 号和26个字母的任意组合,现在需要把字符串中的*号都移动到最左侧,而字符串中的字母移到最右侧并保持相对顺序不变,要求时间和空间复杂度最小。
已邀请:

cpcs - 诚实努力

赞同来自: linxiao Duanexiao yori2015 mochen 与我同行 米修 聿壬 babylls更多 »


时间O(n),空间O(1), 大概这样:倒着扫一遍 遇到字母就从最后开始放 用的是同一块空间。。。最后开头没动过的那些都设置为*。
    int now = s.length();
    for (int i = now - 1; i >= 0; --i) {
             if (s[i] != '*') {
                  s[--now] = s[i];
            }
    }

    for (--now; now >= 0; --now) {
             s[now] = '*';
    }

要回复问题请先登录注册