Java数组高效比较：利用排序与二分查找实现O(N log N)性能优化

import java.util.ArrayList;
import java.util.List;

public class ArrayComparison {

    /**
     * 传统方法：使用嵌套循环比较两个数组元素。
     * 时间复杂度为 O(a.length * b.length)。
     */
    public static List<Integer> giantArmyTraditional(int[] a, int[] b) {
        List<Integer> resultList = new ArrayList<>();
        // 处理特殊情况，如果a数组只有一个0元素，则直接返回[0]
        // (此条件可能源于特定业务需求，通常可省略)
        if (a.length == 1 && a[0] == 0) {
            resultList.add(0);
            return resultList;
        }

        for (int i = 0; i < b.length; i++) {
            int count = 0; // 每次循环b数组元素时重置计数器
            for (int j = 0; j < a.length; j++) {
                if (a[j] >= b[i]) {
                    count++;
                }
            }
            resultList.add(count);
        }
        return resultList;
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5};
        int[] b = {6, 5, 4, 3, 2};
        System.out.println("传统方法结果: " + giantArmyTraditional(a, b)); // 输出: [0, 1, 2, 3, 4]
    }
}

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

public class ArrayComparisonOptimized {

    /**
     * 优化方法：利用排序和二分查找高效比较两个数组元素。
     * 整体时间复杂度为 O(N log N + M log N)，其中N为a的长度，M为b的长度。
     * 当N和M相近时，可简化为 O(N log N)。
     */
    public static List<Integer> giantArmyOptimized(int[] a, int[] b) {
        int aLength = a.length;
        List<Integer> resultList = new ArrayList<>();

        // 步骤1: 对数组 a 进行升序排序
        // 这一步的时间复杂度为 O(N log N)
        Arrays.sort(a);

        // 步骤2: 遍历数组 b 中的每个元素
        // 对每个元素执行二分查找，每次查找的时间复杂度为 O(log N)
        // 总计 M 次查找，因此这部分的时间复杂度为 O(M log N)
        for (int bElement : b) {
            // 步骤3: 在已排序的 a 数组中查找 bElement
            int index = Arrays.binarySearch(a, bElement);

            // 如果 bElement 未在 a 中找到，Arrays.binarySearch 返回一个负值
            // 这个负值是 -(插入点) - 1
            // 因此，实际的插入点是 -index - 1
            if (index < 0) {
                index = -index - 1;
            }
            // 此时的 index 表示：
            // 如果 bElement 在 a 中，index 是其首次出现的位置。
            // 如果 bElement 不在 a 中，index 是它应该被插入的位置，
            // 使得其左侧元素都小于它，右侧元素都大于等于它。

            // 那么，数组 a 中大于等于 bElement 的元素数量就是 a.length - index
            resultList.add(aLength - index);
        }
        return resultList;
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5};
        int[] b = {6, 5, 4, 3, 2};
        System.out.println("优化方法结果: " + giantArmyOptimized(a, b)); // 输出: [0, 1, 2, 3, 4]

        int[] a2 = {10, 20, 30, 40, 50};
        int[] b2 = {15, 35, 60, 5, 30};
        // 预期结果：
        // 15: a中有 [20, 30, 40, 50] 共 4 个 >= 15
        // 35: a中有 [40, 50] 共 2 个 >= 35
        // 60: a中有 [] 共 0 个 >= 60
        // 5:  a中有 [10, 20, 30, 40, 50] 共 5 个 >= 5
        // 30: a中有 [30, 40, 50] 共 3 个 >= 30
        // 结果应为 [4, 2, 0, 5, 3]
        System.out.println("优化方法结果 (示例2): " + giantArmyOptimized(a2, b2));
    }
}