如何优化数组统计逻辑？提升大输入场景下的代码性能

问题拆解 #

给定数组a = [1, 2, 3, 4, 5]和b = [6, 5, 4, 3, 2]，需要返回一个ArrayList，其中每个元素对应b当前元素在a中大于等于它的元素数量，预期输出[0, 1, 2, 3, 4]。

原代码存在两个核心问题：

1. 性能瓶颈：双重循环的时间复杂度为O(n*m)，当数组长度达到十万甚至百万级时，执行效率会断崖式下跌。
2. 冗余逻辑：开头的if (a.length == 1 && a[0] == 0)判断完全多余，不仅覆盖了正常场景（比如a长度为1但元素非0的情况），还可能导致逻辑异常。

优化思路：排序+二分查找 #

通过先排序数组a，再对b的每个元素用二分查找快速定位边界的方式，将时间复杂度降至O(n log n + m log n)，大幅提升大输入场景下的性能。

优化后的代码 #

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Collections;

static List<Integer> giantArmy(int[] a, int[] b) {
    // 提前初始化容量，避免扩容损耗
    List<Integer> result = new ArrayList<>(b.length);
    // 复制并排序数组a，不修改原数组
    int[] sortedA = Arrays.copyOf(a, a.length);
    Arrays.sort(sortedA);
    
    for (int num : b) {
        // 二分查找第一个大于等于num的位置
        int left = 0;
        int right = sortedA.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (sortedA[mid] >= num) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        // 符合条件的元素数量 = 数组总长度 - 边界索引
        result.add(sortedA.length - left);
    }
    return result;
}

代码说明 #

• 排序数组a：对a进行升序排序，为二分查找提供有序基础。这里用Arrays.copyOf避免修改原数组，若业务允许直接修改原数组，可省略复制步骤进一步提升效率。
• 手动实现二分查找：相比Collections.binarySearch，手动实现更灵活，直接定位第一个大于等于目标值的边界索引。
• 计算符合条件的数量：排序后的a中，从边界索引到末尾的所有元素都满足>=目标值，因此数量为数组长度 - 边界索引。

测试验证 #

用你的测试用例验证：

• 排序后的a为[1,2,3,4,5]
• 遍历b的每个元素：
  • 6：边界索引为5，5-5=0
  • 5：边界索引为4，5-4=1
  • 4：边界索引为3，5-3=2
  • 3：边界索引为2，5-2=3
  • 2：边界索引为1，5-1=4
• 最终结果为[0,1,2,3,4]，完全符合预期。

内容的提问来源于stack exchange，提问作者Neel Chavan