把 01 数组中所有 1 聚到一起的最少移动次数
哪些公司问过
答案要点
- 先明确移动定义:相邻交换还是任意两元素交换,解法不同
- 相邻交换:记 1 的下标 pi,令 qi=pi−i,最少次数为各 qi 到其中位数的距离和
- qi 天然非递减,直接取中间元素,时间 O(n)
- 任意交换:窗口长为 1 的总数 k,答案为 k 减窗口内 1 的最大数量
- 边界:没有 1 或只有一个 1 时答案为 0
易错点
- 没确认移动定义就写代码,把相邻交换和任意交换混淆
- 直接对原下标 pi 求中位数,忘记减去 i 的偏移
- 距离和可能很大,用 int 累加导致溢出
面试官常见追问
- 为什么取中位数能让距离和最小?
- 如果数组是环形的怎么办?
- 如果只要求把其中 k 个 1 聚在一起呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 数组和链表的区别与适用场景173 场
- 经典算法题:最长回文子串、无重复最长子串、最大子数组和141 场
- 合并有序数组与合并区间66 场
- 三数之和:排序加双指针50 场
- 字符串相加(大数加法)20 场
- 字符串匹配:KMP 算法18 场
- 字符串反转的实现与注意事项17 场
- 接雨水问题的三种解法14 场
- 螺旋矩阵遍历14 场
- 两数之和的几种解法12 场