Issue
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;
}
Solution
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
Answered By - 英語は苦手
Answer Checked By - Robin (JavaFixing Admin)
