原地逆序一个数组
哪些公司问过
卓驭科技1
答案要点
- 双指针 i、j 从两端向中间移动,i < j 时交换后 i++、j--
- 共交换 n/2 次,时间 O(n),额外空间 O(1)
- 奇数长度时中间元素不动,空数组和单元素数组无需特判
- C++ 可用 std::reverse,Java 的 List 可用 Collections.reverse
- 找第 k 小可用快速选择(平均 O(n))或大小为 k 的大顶堆(O(n log k))
易错点
- 遍历整个数组都做交换,前一半换过去后一半又换回来,数组恢复原样
- 下标从 n 开始而不是 n-1,越界访问
- 快速选择后直接返回当前位置,忘了元素已被移动,不是原下标
面试官常见追问
- 大小为 10000 的数组如何找到第 100 小的数的下标?
- 如何把数组循环右移 k 位且不用额外空间?
- 能用异或交换代替临时变量吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 数组和链表的区别与适用场景173 场
- 经典算法题:最长回文子串、无重复最长子串、最大子数组和141 场
- 合并有序数组与合并区间66 场
- 三数之和:排序加双指针50 场
- 字符串相加(大数加法)20 场
- 字符串匹配:KMP 算法18 场
- 字符串反转的实现与注意事项17 场
- 接雨水问题的三种解法14 场
- 螺旋矩阵遍历14 场
- 两数之和的几种解法12 场