在Java数组中查找最接近零的数

1. 概述

本文将深入探讨在Java数组中查找最接近零的数的问题。例如，给定数组[1, -3, 2, -2, 4]，最接近零的数是1。我们将研究多种高效解决方案，提升问题解决能力。

2. 查找最接近零的数的几种方法

我们将讨论三种方案，各有优劣：

• 暴力解法
• 排序+二分查找优化方案
• 优先队列方案

2.1. 暴力解法

这种方法简单粗暴：遍历数组，计算每个元素与零的绝对差值，并跟踪最小差值。当两个数绝对值相同时，优先选择正数以确保结果一致。

实现代码：

public static int findClosestToZero(int[] arr) throws IllegalAccessException {
    if (arr == null || arr.length == 0) {
        throw new IllegalAccessException("数组不能为null或空");
    }

    int closest = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if ((Math.abs(arr[i]) < Math.abs(closest)) ||
          ((Math.abs(arr[i]) == Math.abs(closest)) && (arr[i] > closest))) {
            closest = arr[i];
        }
    }
    return closest;
}

✅ 时间复杂度O(n)，是此问题的最优解
❌ 多次查询时效率较低

测试用例：

@Test
void whenFindingClosestToZeroWithBruteForce_thenResultShouldBeCorrect()
  throws IllegalAccessException {
    int[] arr = {1, 60, -10, 70, -80, 85};
    assertEquals(1, BruteForce.findClosestToZero(arr));
}

2.2. 排序+二分查找方案

这个方案先对数组排序（按绝对值升序），再用二分查找定位最接近零的元素。注意：虽然二分查找是O(log n)，但排序步骤需要O(n log n)，整体复杂度变为O(n log n)。

实现代码：

public static int findClosestToZero(int[] arr) {
    if (arr == null || arr.length == 0) {
        throw new IllegalArgumentException("数组不能为null或空");
    }

    Arrays.sort(arr);
    int closestNumber = arr[0];
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (Math.abs(arr[mid]) < Math.abs(closestNumber)) {
            closestNumber = arr[mid];
        }

        if (arr[mid] < 0) {
            left = mid + 1;
        } else if (arr[mid] > 0) {
            right = mid - 1;
        } else {
            return arr[mid];
        }
    }
    return closestNumber;
}

⚠️ 排序会修改原数组
✅ 适合需要多次查询的场景

测试用例：

@Test
void whenFindingClosestToZeroWithBruteForce_thenResultShouldBeCorrect() throws IllegalAccessException {
    int[] arr = {1, 60, -10, 70, -80, 85};
    assertEquals(1, SortingAndBinarySearch.findClosestToZero(arr));
}

执行流程：

1. 数组排序为[-80, -10, 1, 60, 70, 85]
2. 初始化closestNumber = -80
3. 二分查找过程中发现1更接近零，更新结果
4. 最终确认1为最接近零的数

2.3. 优先队列方案

另一种方案是利用优先队列（堆）高效查找，无需排序整个数组。通过维护一个大小为k的堆，动态保留最接近零的k个数。

实现代码：

public static int findClosestToZeroWithPriorityQueue(int[] arr, int k) {
    if (arr == null || arr.length == 0 || k <= 0) {
        throw new IllegalArgumentException("输入参数无效");
    }

    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Math.abs(b) - Math.abs(a));

    for (int num : arr) {
        pq.offer(num);
        if (pq.size() > k) {
            pq.poll();
        }
    }
    return pq.peek();
}

✅ 适合需要查找前k个最接近零的数
❌ 比暴力解法稍慢（O(n log k)）

测试用例：

@Test
void whenFindingClosestToZeroWithBruteForce_thenResultShouldBeCorrect()
  throws IllegalAccessException {
    int[] arr = {1, 60, -10, 70, -80, 85};
    assertEquals(1, PriorityQueueToZero.findClosestToZeroWithPriorityQueue(arr, 1));
}

执行流程（k=1时）：

1. 初始化空堆
2. 添加1（堆：[1]）
3. 60绝对值更大，跳过
4. -10绝对值大于1，跳过
5. 后续元素绝对值均大于1，均跳过
6. 最终堆顶元素1即为结果

3. 方案对比

方案	时间复杂度	适用场景	优缺点
暴力解法	O(n)	单次查询	✅ 最快实现 ❌ 多次查询效率低
排序+二分	O(n log n)	多次查询	✅ 查询效率高 ❌ 需要额外排序 ⚠️ 修改原数组
优先队列	O(n log k)	查找前k个	✅ 灵活支持k值 ❌ 比暴力解法稍慢

4. 总结

本文探讨了在Java数组中查找最接近零的数的三种方案：

1. 暴力解法：简单高效，适合单次查询
2. 排序+二分：适合需要多次查询的场景
3. 优先队列：灵活支持查找前k个最接近的数

每种方案都有其适用场景，实际开发中应根据具体需求选择。例如：

• 单次查询 → 暴力解法
• 需要多次查询 → 排序+二分
• 需要前k个结果 → 优先队列

本文代码示例可在GitHub获取。