题解 | #移动字母#
移动字母
http://www.nowcoder.com/practice/1e5655d7c7be4566b386eb925afcb206
移动字母
描述
给定一个只包含小写字母的字符串s，牛牛想将这个字符串中的所有'a'字母全部移动到字符串的末尾，而且保证其它字符的相对顺序不变。其中字符串s的长度<=1e6。
给定一个只包含小写字母的字符串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)$
