仅包含X/Y/Z的2字符字符串数组线性时间排序方法咨询

核心思路 #

由于待排序字符串仅由3种字符组成、长度固定为2，所有可能的取值一共只有 3*3=9 种，完全可以用计数排序实现严格的线性时间复杂度，规避比较类排序O(nlogn)的时间下限。

实现步骤 #

• 先给三种字符映射整数权重：X→0、Y→1、Z→2，每个长度为2的字符串可以转换为唯一的0~8之间的整数，转换公式为 映射值 = 首字符权重*3 + 次字符权重
• 初始化长度为9的计数数组，所有元素初始值为0，遍历原数组统计每种字符串出现的次数，对应计数数组下标数值+1
• 按下标从小到大遍历计数数组，根据每个位置的计数值，往结果数组中填充对应数量的字符串即可

示例代码（C# 版本） #

public string[] SortSpecialArr(string[] arr)
{
    // 字符权重映射
    Dictionary<char, int> charMap = new Dictionary<char, int>()
    {
        {'X', 0}, {'Y', 1}, {'Z', 2}
    };
    int[] count = new int[9];
    // 第一次遍历统计次数，时间复杂度O(n)
    foreach(string s in arr)
    {
        int index = charMap[s[0]] * 3 + charMap[s[1]];
        count[index]++;
    }
    string[] res = new string[arr.Length];
    int pos = 0;
    // 生成结果数组，时间复杂度O(n)，计数数组遍历开销为常数可忽略
    for(int i = 0; i < 9; i++)
    {
        char first = (i / 3) switch {0 => 'X', 1 => 'Y', 2 => 'Z'};
        char second = (i % 3) switch {0 => 'X', 1 => 'Y', 2 => 'Z'};
        string val = $"{first}{second}";
        for(int j = 0; j < count[i]; j++)
        {
            res[pos++] = val;
        }
    }
    return res;
}

复杂度说明 #

• 时间复杂度：O(n)，仅需要2次遍历原数组，计数数组遍历开销为固定常数，不随输入规模n变化
• 空间复杂度：O(1)（除结果数组外），计数数组长度固定为9，不会随输入规模扩大而增加

内容的提问来源于stack exchange，提问作者Inf