移动字母

描述
给定一个只包含小写字母的字符串s，牛牛想将这个字符串中的所有'a'字母全部移动到字符串的末尾，而且保证其它字符的相对顺序不变。其中字符串s的长度<=1e6。
示例
输入："abcavv"
返回值："bcvvaa"

方法一

思路分析

本题容易想到的是先统计字符串中所有的字母a的个数，在循环遍历统计的过程中，设置另一个字符串temp，当遍历所给字符串s时，如果不是字母a，那么将其赋值给字符串temp的一个位置，最后根据所统计到的字母a的个数，在字符串temp后面加上相应数量的字母a，即可

核心代码 

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string change(string s) {
        // write code here
        int n=s.size();
        string temp;
        int count=0;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='a')
                count++;
            else temp+=s[i];
        }
        temp.append(count,'a');
        return temp;
    }
};

复杂度分析

  • 时间复杂度：需要遍历字符串，因此时间复杂度为$O(len(s))$
  • 空间复杂度：需要定义一个字符串，因此空间复杂度为$O(len(s))$

方法二

思路分析

根据方法一的思路，需要额外的存储空间，不能在所给字符串的基础上直接进行变换，因此方法二不单独设置额外的空间，直接利用所给的字符串进行移动，其基本思想为：

图解


核心代码 

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string change(string s) {
        // write code here
        int n=s.size();
        int index=0;
        int index_a=s.find('a');//找到第一个字符是a的下标
        index=index_a+1;//从第一个a的位置的下一个位置开始遍历
        for(;index<n;)
        {
           if(s[index]!='a')
             {
                 char temp=s[index];//交换两个字符
                 s[index]=s[index_a];
                 s[index_a]=temp;
                 index_a=s.find('a');//指向字符串中第一个字母为a的位置
                
            }
        index++;//遍历字符串        
        }
        return s;
    }
};
复杂度分析
  • 时间复杂度：设置两个指示位置的指针，遍历一次字符串，时间复杂度为$O(len(s))$
  • 空间复杂度：不需要额外的空间，空间复杂度为$O(1)$