题解 | #移动字母#

题意整理

给定一个只包含小写字母的字符串s。
将所有'a'字符移到末尾，并且保证其他字符相对位置不变。

方法一（直接复制）

1.解题思路

将字符串转化为字符数组。
遍历字符数组，将所有非'a'字符按顺序填到字符数组。
将剩下的位置填满'a'字符。
再将字符数组转化为字符串返回。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String change (String s) {
        //转化为字符数组
        char[] arr=s.toCharArray();
        int n=arr.length;
        //赋值游标
        int id=0;
        for(int i=0;i<n;i++){
            //如果不是'a',按顺序填到arr数组中
            if(arr[i]!='a'){
                arr[id++]=arr[i];
            }
        }
        //剩下位置，补满'a'
        for(int i=id;i<n;i++){
            arr[i]='a';
        }
        return String.valueOf(arr);
    }
}

3.复杂度分析

时间复杂度：只需要一次线性遍历，所以时间复杂度是 $O(n)$ 。
空间复杂度：需要额外长度为n的字符数组，所以空间复杂度是 $O(n)$ 。

方法二（双指针）

1.解题思路

将字符串转化为字符数组。
遍历字符数组，只要是非'a'字符，就与j处字符交换，并且j指针后移。
将字符数组转化为字符串返回。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String change (String s) {
        //初始化字符数组
        char[] arr=s.toCharArray();
        int n=arr.length;
        //定义指针j，指向最左边a出现的位置
        int j=0;
        for(int i=0;i<n;i++){
            //如果i对应字符不是'a'，就与j交换，同时j后移一位
            if(arr[i]!='a'){
                char c=arr[i];
                arr[i]=arr[j];
                arr[j++]=c;
            }
        }
        return String.valueOf(arr);
    }
}

3.复杂度分析

时间复杂度：只需要一次线性遍历，所以时间复杂度是 $O(n)$ 。
空间复杂度：需要额外长度为n的字符数组，所以空间复杂度是 $O(n)$ 。