字符串排序（HJ19）

字符串排序 题解

题目描述

https://www.nowcoder.com/share/jump/5832603751775720180207

给定一个由可见字符和空格组成的字符串，按以下规则排序： 1. 按字母表顺序排序（不区分大小写） 2. 同一字母的大小写同时存在时，按输入顺序排列 3. 非字母字符保持原位置不参与排序

示例： - 输入：BabA，输出：aABb - 输入：Hello NowCoder!，输出：CdeeHllNooorw!

---

解法

问题类型：稳定排序 + 原位重建

思路： 1. 提取所有字母字符 2. 按小写形式排序（Python sort 是稳定的，同字母保持原顺序） 3. 遍历原字符串，按顺序放回排序后的字母，非字母保持不变

代码

s = input()

arr = [ch for ch in s if ch.isalpha()]
arr.sort(key=str.lower)

res = []
cur = 0
for ch in s:
    if ch.isalpha():
        res.append(arr[cur])
        cur += 1
    else:
        res.append(ch)

print(''.join(res))

时间复杂度：O(n log n) 空间复杂度：O(n)

注意：Python 的 sort 是稳定排序，相同键值的元素保持相对顺序，这正是题目要求的”同字母保持输入顺序”。