LeetCode 补充题 219. 有序数组中绝对值最小的元素
题目描述
给定一个按非降序排列的非空整数数组
nums，返回数组中绝对值最小的元素，保留该元素原来的正负号。若两个元素的绝对值相同，约定返回数值较大的那个。例如
-2和2同时最接近零时，返回2。请利用数组的有序性，在 $O(\log n)$ 时间、$O(1)$ 额外空间内完成查找。
示例 1：
输入：nums = [-10,-5,-2,0,3,6,9]
输出：0
示例 2：
输入：nums = [-8,-3,-1,2,4,7]
输出：-1
示例 3：
输入：nums = [-5,-2,2,9]
输出：2
解释：-2 和 2 的绝对值相同，按约定返回较大的 2。
提示：
-
nums.length >= 1。 -
nums已按非降序排列，允许出现重复元素。 - 数组可能全为非负数、全为非正数，也可能同时包含负数和正数。
- 元素可能取到所用整数类型的最小值，比较绝对值时需避免溢出。
题意分析
要找的是离
0最近的元素，而不是数组中的最小元素，也不是返回绝对值本身。例如第二个示例应返回-1，不能返回1。有序性让候选范围大幅缩小：负数中越靠右越接近零，正数中越靠左越接近零。因此没有零时，只需比较最后一个负数和第一个正数。
解法：二分定位零点两侧的候选
核心思路
[!blue]
若
nums[0] >= 0，所有元素均非负，首元素就是答案；若nums[n - 1] <= 0，所有元素均非正，末元素就是答案。这两种情况也覆盖单元素数组。剩下的情况一定同时存在负数和正数。用闭区间
[left, right]二分查找0：中点等于零时直接返回；中点为负数时向右查找，为正数时向左查找。如果没有找到零，循环结束后
left = right + 1，其中right指向最后一个负数，left指向第一个正数。前面的分类处理保证两者都在数组范围内，答案只可能是这两个候选之一。Java 先将负数转为
long再取负，避免Integer.MIN_VALUE溢出。Go 不对负数候选取负，而是比较nums[right] > -nums[left]：右侧候选一定为正数，对它取负不会溢出。两种写法在绝对值相同时都会返回正数候选，符合题目约定。
解题步骤
- 检查首、末元素，处理全非负和全非正的数组。
- 在闭区间
[0, n - 1]中二分查找0；遇到零立即返回。- 区间为空后，取
nums[right]和nums[left]作为仅有的两个候选。- 安全比较绝对值，返回较小者；绝对值相等时返回正数候选。
代码实现
class Solution {
public int findMinAbs(int[] nums) {
int n = nums.length;
if (nums[0] >= 0) {
return nums[0];
}
if (nums[n - 1] <= 0) {
return nums[n - 1];
}
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == 0) {
return 0;
} else if (nums[mid] < 0) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -(long) nums[right] < nums[left] ? nums[right] : nums[left];
}
}
func findMinAbs(nums []int) int {
n := len(nums)
if nums[0] >= 0 {
return nums[0]
}
if nums[n-1] <= 0 {
return nums[n-1]
}
left, right := 0, n-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == 0 {
return 0
} else if nums[mid] < 0 {
left = mid + 1
} else {
right = mid - 1
}
}
if nums[right] > -nums[left] {
return nums[right]
}
return nums[left]
}
复杂度分析
设数组长度为 $n$。
- 时间复杂度：$O(\log n)$。每轮二分排除约一半搜索区间；全非负或全非正时直接返回。
- 空间复杂度：$O(1)$。仅使用边界和中点等常数个变量。
关键点总结
[!green]
- 绝对值在整个有序数组上并不单调，但元素与零的大小关系是单调的，可以据此二分。
- 最接近零的候选一定在正负分界点两侧；存在零时，零就是最优答案。
- 比较绝对值时避免直接对最小整数取负，返回时保留原元素的符号。
易错点总结
[!yellow]
- 不先处理全非负、全非正的情况，二分结束后直接访问两侧候选可能越界。
- Java 中应先转换再取负：
-(long) nums[right]；先对int取负再转换仍会溢出。- Go 中直接对最小
int取负同样可能溢出；当前实现只对正数候选取负。- 两个候选绝对值相同时，不能随意返回负数，要遵守返回较大元素的约定。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 2239. 找到最接近 0 的数字 | 简单 | 同样寻找距离零最近的原元素，绝对值相同时取较大值。原题数组不保证有序，通常用 $O(n)$ 遍历；本题数组已排序，可以用 $O(\log n)$ 二分查找。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！