优化双数组循环：利用排序与二分查找提升性能

import Java.util.ArrayList; import java.util.List;  public class ArrayComparison {      /**      * 传统嵌套循环方法，统计数组a中大于等于b中每个元素的数量。      * 性能较低，时间复杂度为 O(m*n)。      *      * @param a 整数数组a      * @param b 整数数组b      * @return 存储统计结果的列表      */     public static List<Integer> giantArmyInefficient(int a[], int b[]) {         List<Integer> list = new ArrayList<>();         // 针对特定边界条件（a只有一个0元素），可以提前返回，但这不是核心优化点         if (a.Length == 1 && a[0] == 0) {             list.add(0);             return list;         }          int count;         for (int i = 0; i < b.length; i++) { // 外层循环遍历b             count = 0; // 每次对b[i]的统计都需要重置计数器             for (int j = 0; j < a.length; j++) { // 内层循环遍历a                 if (a[j] >= b[i]) {                     count++;                 }             }             list.add(count);         }         return list;     }      public static void main(String[] args) {         int[] arrA = {1, 2, 3, 4, 5};         int[] arrB = {6, 5, 4, 3, 2};         System.out.println("Inefficient result: " + giantArmyInefficient(arrA, arrB));     } }

import java.util.ArrayList; import java.util.Arrays; import java.util.List;  public class ArrayComparisonOptimized {      /**      * 优化后的方法，利用排序和二分查找统计数组a中大于等于b中每个元素的数量。      * 时间复杂度为 O(n log n + m log n)。      *      * @param a 整数数组a      * @param b 整数数组b      * @return 存储统计结果的列表      */     public static List<Integer> giantArmyOptimized(int a[], int b[]) {         int aLength = a.length;         List<Integer> result = new ArrayList<>();          // 步骤1: 对数组a进行排序         Arrays.sort(a); // 时间复杂度 O(n log n)          // 步骤2: 遍历数组b，并对每个元素在a中进行二分查找         for (int target : b) { // 循环m次             // 步骤3: 在已排序的a中查找target的插入点             int index = Arrays.binarySearch(a, target); // 每次查找 O(log n)              // 如果target不存在，index为负数，表示插入点             if (index < 0) {                 index = -index - 1; // 转换为实际的插入点，即小于target的元素数量             } else {                 // 如果target存在，需要找到第一个大于等于target的元素的索引。                 // Arrays.binarySearch可能返回任意一个匹配项的索引。                 // 为了正确统计，我们需要找到所有等于target的元素的起始位置。                 // 简单的做法是，如果找到，我们继续向左查找，直到找到第一个等于target的元素或越界。                 // 但对于“大于等于”的统计，直接使用返回的index是可行的，因为我们关心的是其右侧元素的数量。                 // 如果存在多个相同元素，binarySearch可能返回其中任意一个的索引。                 // 但由于我们最终是计算 aLength - index，只要index指向的是一个有效的“分界点”即可。                 // 更严谨的做法是找到第一个等于target的元素的索引，但对于本问题，                 // Arrays.binarySearch返回的任何一个target的索引，其左侧都是小于target的，其右侧（包括它自己）都是大于等于target的。                 // 因此，如果index >= 0，它已经是大于等于target的第一个元素（或其中之一）的索引。             }              // aLength - index 即为数组a中大于或等于target的元素的数量             result.add(aLength - index);         }         return result;     }      public static void main(String[] args) {         int[] arrA = {1, 2, 3, 4, 5};         int[] arrB = {6, 5, 4, 3, 2};         System.out.println("Optimized result: " + giantArmyOptimized(arrA, arrB)); // 预期输出: [0, 1, 2, 3, 4]     } }

Optimized result: [0, 1, 2, 3, 4]

[1 2 3 4 5]                 (number of elements >= 6) = 0          x      (number of elements >= 5) = 1        x x      (number of elements >= 4) = 2      x x x      (number of elements >= 3) = 3    x x x x      (number of elements >= 2) = 4  x x x x x      (number of elements >= 1) = 5  x x x x x      (number of elements >= 0) = 5