字符串变换的最小交换次数
哪些公司问过
地平线机器人1
答案要点
- 先确认是任意位置交换还是相邻交换,两种问题解法不同
- 字符不重复时,用哈希表把目标位置映射成一个排列
- 任意交换:最小次数 = n − 环的个数,O(n) 求解
- 相邻交换:最小次数 = 排列的逆序对数,归并排序或树状数组 O(n log n)
- 先校验长度和字符集一致,不一致直接判无解
易错点
- 不确认交换规则就直接回答,混淆环分解和逆序对两种答案
- 用模拟逐个交换且每次线性查找,复杂度退化为 O(n²)
- 没有校验两串字符集是否一致
面试官常见追问
- 为什么一个长度为 m 的环需要 m−1 次交换?
- 如果字符可以重复呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。