描述

输入描述：

Lily使用的图片包括"A"到"Z"、"a"到"z"、"0"到"9"。输入字母或数字个数不超过1024。

输出描述：

Lily的所有图片按照从小到大的顺序输出

示例

输入：
Ihave1nose2hands10fingers
输出：
0112Iaadeeefghhinnnorsssv

知识点：排序，字符串

难度：⭐⭐⭐

题解

方法一：快速排序

图解：

解题思路：

对字符的ASCII码的大小进行快速排序

算法流程：

• 将每个字符转为int类型的Ascii码，通过ASCII码的大小进行快速排序
• 通过快排的填坑法进行部分排序并返回排序后的分割点，之后再重复进行快排
  • 最左边的元素作为基准元素，并保存该值
  • 维护双指针指针，右指针向左寻找第一个小于基准值的元素，并将该元素填入基准元素
  • 左指针向右寻找第一个大于基准值p的元素, 并将该元素的值填入右指针的位置
  • 直到左右指针重合，此时再将之前保存的基准元素的值填入左指针和右指针指向的位置，并返回左指针（或右指针）的索引

Java 版本代码如下：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.nextLine();
            System.out.println(solution(s));
        }
    }

    private static String solution(String str) {
        if(str == null || str.length() == 0) {
            return "";
        }
        char[] arr = str.toCharArray();
        int[] ascii = new int[str.length()];
        // 转为int类型的Ascii码，通过ASCII码的大小进行顺序排序
        for(int i = 0; i < arr.length; i++) {
            ascii[i] = (int) arr[i];
        }
        quickSort(ascii, 0, arr.length - 1);
        // 转为字符
        for(int i = 0; i < ascii.length; i++) {
            arr[i] = (char) ascii[i];
        }
        return String.valueOf(arr);
    }

    private static void quickSort(int[] arr, int lo, int hi) {
        if(lo >= hi) {
            return;
        }
        // 找出排序后的分割点
        int p = partition(arr, lo, hi);
        // 分治进行快排
        quickSort(arr, lo, p - 1);
        quickSort(arr, p + 1, hi);
    }

    // 填坑法，返回排序后的基准位索引
    private static int partition(int[] arr, int lo, int hi) {
        int p = arr[lo];
        while(lo < hi) {
            // 右指针向左寻找第一个小于基准值的元素，并将该元素填入基准元素
            while(lo < hi && arr[hi] >= p) {
                hi--;
            }
            // 填坑
            arr[lo] = arr[hi];
            // 左指针向右寻找第一个大于基准值p的元素, 并将该元素的值填入右指针的位置
            while(lo < hi && arr[lo] <= p) {
                lo++;
            }
            arr[hi] = arr[lo];
        }
        // 最后lo == hi
        arr[lo] = p;
        return lo;
    }
}

复杂度分析：

时间复杂度：$O(NlogN)O(NlogN)$，快排最坏情况是 O(N^2)，平均时间复杂度是 O(NlogN)，这里的n和logn, 分别代表了调用栈的深度，和完成每层调用需要的时间，最坏的情况是每次基准值都是最左边的元素，N为字符串长度

空间复杂度：$O(N)O(N)$，递归所需要调用栈的深度，也需要数组来维护结果，N为字符串长度

方法二：

解题思路：

通过数组的下标为字符的ASCII码，类似位图来表示是否存在该字符

算法流程：

• 维护一个数组，用来统计每个字符出现的次数，数组下标为字符的ASCII码
• 遍历数字 0 到最后字母 z 的ASCII码，这样就可以按顺序根据：从数组的出现频次来填充多少个该字符，并且顺序是升序的

Java 版本代码如下：

import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String str = in.nextLine();
            System.out.println(solution(str));
        }
    }
    private static String solution(String str) {
        // 统计每个字符出现的次数，数组下标为字符的ASCII码
        // 数字和字母的ASCII码在128以内
        int[] arr = new int[128];
        for(int i = 0; i < str.length(); i++) {
            int count = (int) str.charAt(i);
            arr[count]++;
        }
        StringBuilder res = new StringBuilder();
        //从'0'开始输出
        for(int i = 48; i < arr.length; ++i) {
            // 只处理出现过的元素
            if(arr[i] != 0) {
                // 根据出现次数，填充结果
                while(arr[i]-- > 0) {
                    // 根据数组下标i代表的ASCII码，转为字符
                    res.append((char)i);
                }
            }
        }
        return res.toString();
    }

}

复杂度分析：

时间复杂度：$O(N)O(N)$，需要遍历处理字符串转为ASCII码，N为字符串长度

空间复杂度：$O(N)O(N)$，长度为 N 的StringBuilder 用来保存结果