I have two arrays array a = [1, 2, 3, 4, 5] and array b = [6, 5, 4, 3, 2] and i am returning a array list which contains a count where i taking elements of array b and checking what elements of array a are greater than or equal to the each element of array b, and i am storing this in count varible and later adding each count to the list so the output will be list = [0, 1, 2, 3, 4], but the code i've written is lacking in the performance for larger sets of input and not giving supposed answer's in the expected way any idea of how can i improve my code to improve the performance

static List<Integer> giantArmy(int a[],int b[]){
        List<Integer> list = new ArrayList<Integer>();
        if (a.length == 1 && a[0] == 0) {
            list.add(0);
            return list;
        }

        int count = 0;
        for (int i = 0; i < b.length; i  ) {
            for (int j = 0; j < a.length; j  ) {
                if (a[j] >= b[i]) {
                    count  ;
                }
            }
            list.add(count);
            count = 0;
        }
        return list;
    }

CodePudding user response：

An implementation of Basil Bourque's comment. This is O(n log n). (Sort is O(n log n) and binary search O(log n) repeated n times)

static List<Integer> giantArmy(int a[],int b[]){
    int aLength = a.length;
    List<Integer> result = new ArrayList<>();
    Arrays.sort(a);
    for (int i : b) {
        int index = Arrays.binarySearch(a, i);
        if (index < 0)
            index = -index - 1;
        result.add(aLength - index);
    }
    return result;
}

public static void main(String[] args) {
    System.out.println(giantArmy(new int[] {1, 2, 3, 4, 5}, new int[] {6, 5, 4, 3, 2}));
}

output:

[0, 1, 2, 3, 4]

A binary search of n for the sorted a yields the number of elements of a whose number of elements to the right of the position found is greater than or equal to n.

[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