O(n)复杂度下合并n个字符串并筛选字母排序的技术咨询

嘿，这个问题我之前做编程挑战的时候也碰到过类似的，咱们一步步拆解来解决～

先理清楚核心问题 #

你说的需求是合并n个字母数字字符串，只留字母字符，最后排序，还要满足O(n)复杂度。首先得明确：这里的O(n)大概率指时间复杂度（空间如果要严格O(n)也能做到，后面会说）。你的初始思路是先拼接再过滤，但这里有个坑——常规的排序算法比如快排是O(k log k)（k是过滤后的字母总数），这肯定达不到O(n)的要求，所以得换个思路。

符合O(n)复杂度的解法：计数排序 #

因为字母的数量是固定的（小写26个，加上大写总共52个），这是个有限且固定大小的集合，所以用计数排序就完美了，这是典型的线性时间排序算法，刚好符合要求。

具体步骤拆解 #

• 第一步：初始化计数数组
  先搞一个大小为52的数组（区分大小写的话）或者26的数组（不区分大小写就用这个），初始值全设为0。比如区分大小写的话，A-Z对应索引0-25，a-z对应26-51。
• 第二步：遍历所有字符串，统计字母出现次数
  逐个过每个输入字符串的每个字符：
  • 如果是大写字母，算索引：当前字符的ASCII码 - 'A'的ASCII码
  • 如果是小写字母，算索引：26 + 当前字符的ASCII码 - 'a'的ASCII码
  • 碰到非字母直接跳过，对应计数数组的位置加1就行
    这一步的时间是O(n)，n是所有输入字符串的总字符数，完全符合要求。
• 第三步：根据计数数组生成排序后的结果
  按顺序（比如先大写A到Z，再小写a到z）遍历计数数组，把每个字母重复对应次数，拼起来就是最终的排序字符串。这一步时间是O(k)，k是过滤后的字母总数，而k肯定小于等于n，所以整体还是O(n)。

代码示例（JavaScript实现，其他语言逻辑一致） #

function mergeAndSortStrings(strings) {
  // 初始化计数数组，覆盖大小写字母
  const count = new Array(52).fill(0);
  
  for (const str of strings) {
    for (const char of str) {
      const charCode = char.charCodeAt(0);
      // 处理大写字母（ASCII 65-90）
      if (charCode >= 65 && charCode <= 90) {
        count[charCode - 65]++;
      } 
      // 处理小写字母（ASCII 97-122）
      else if (charCode >= 97 && charCode <= 122) {
        count[26 + charCode - 97]++;
      }
      // 非字母直接跳过，不用管
    }
  }
  
  // 生成最终的排序字符串
  let result = '';
  // 先拼接大写字母
  for (let i = 0; i < 26; i++) {
    result += String.fromCharCode(65 + i).repeat(count[i]);
  }
  // 再拼接小写字母
  for (let i = 26; i < 52; i++) {
    result += String.fromCharCode(97 + i - 26).repeat(count[i]);
  }
  
  return result;
}

// 测试用例
const testStrings = ["a1B2c3", "XyZ9", "Hello123World"];
console.log(mergeAndSortStrings(testStrings)); 
// 输出：BCHWdellloorxyz

关于空间复杂度的说明 #

如果题目要求空间复杂度也是O(n)，这个解法完全达标：计数数组是固定大小的，属于O(1)（因为字母数量固定，不会随输入规模变大而变大），结果字符串的长度是k≤n，所以整体空间是O(n)。

为啥初始思路达不到O(n)？ #

如果先拼接过滤再用常规排序（比如语言自带的sort()方法），排序那一步的时间复杂度是O(k log k)，当k很大的时候，这就超过了O(n)的要求。而计数排序刚好利用了字母数量有限的特性，把排序步骤降到了线性时间，完美解决问题。

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