A/B 字符串相邻交换使 A 全在左的最少步数
哪些公司问过
答案要点
- 最少相邻交换次数等于逆序对数,即「B 在 A 前」的对数
- 每次交换最多消除一个逆序对,且存在相邻 BA 时必能消除一个
- 一次遍历维护已见 B 的个数,遇到 A 就累加
- 时间 O(n),空间 O(1),结果可达 n²/4 量级需用 64 位
- 等价做法:每个 A 的当前位置与其目标位置之差求和
易错点
- 直接模拟冒泡交换,复杂度 O(n²)
- 累加结果用 32 位整数,长串时溢出
- 只统计 A 的个数,没有转化为逆序对
面试官常见追问
- 任意整数数组排成升序的最少相邻交换次数?
- 如果 A 全在左或 B 全在左都可以,取最小?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 数组和链表的区别与适用场景173 场
- 经典算法题:最长回文子串、无重复最长子串、最大子数组和141 场
- 合并有序数组与合并区间66 场
- 三数之和:排序加双指针50 场
- 字符串相加(大数加法)20 场
- 字符串匹配:KMP 算法18 场
- 字符串反转的实现与注意事项17 场
- 接雨水问题的三种解法14 场
- 螺旋矩阵遍历14 场
- 两数之和的几种解法12 场