面试题库 › Java 后端 › A/B 字符串相邻交换使 A 全在左的最少步数

A/B 字符串相邻交换使 A 全在左的最少步数

难度 ★★☆在 1 场真实面经中被问到 方向:Java 后端考点:数组与字符串

哪些公司问过

转转1

常见岗位:Java 后端

答案要点

  1. 最少相邻交换次数等于逆序对数,即「B 在 A 前」的对数
  2. 每次交换最多消除一个逆序对,且存在相邻 BA 时必能消除一个
  3. 一次遍历维护已见 B 的个数,遇到 A 就累加
  4. 时间 O(n),空间 O(1),结果可达 n²/4 量级需用 64 位
  5. 等价做法:每个 A 的当前位置与其目标位置之差求和

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题