Блог

Учитывая два списка массивов A и B, A = {3,4,5] и B = [4,7], посчитайте, сколько чисел в A меньше или равно каждому элементу в B. В этом случае B.get(0)= 4 имеет в A на 2 значения меньше или равно, т.е. 3 и 4, аналогично 7 имеет 3 значения. Таким образом, функция должна возвращать list =[2,3]. Я решил этот вопрос, используя два цикла for, которые работают для меньших входных данных, однако по мере увеличения размера производительность снижается.

 import java.util.*;
public class checkDiff{
public static void check(List<Integer> A, List<Integer> B) {
    List<Integer> result=new ArrayList<Integer>();
    for(int i=0;i<B.size();i  ){
        int count=0;
        for(int j=0;j<A.size();j  ){
            if(A.get(j)<=B.get(i)){
                 count  ;
            }           
        }
    result.add(i,count);
    }
   for(int x:result){
    System.out.println(x);
   }

}

 public static void main(String []args){
     List<Integer> A=new ArrayList<Integer>();
     List<Integer> B=new ArrayList<Integer>();
    A.add(3);
    A.add(4);
    A.add(7);
    B.add(4);
    B.add(7);
    check(A,B);
    
 }
 }
  

Есть ли какой-либо способ оптимизировать этот код.Пожалуйста, помогите.

Дело в том, что вы берете массив, который не отсортирован по значению. Следовательно, вам придется проверить все возможные комбинации, и вы не сможете ускорить этот процесс, если только вы не используете отсортированный список или не используете структуру данных, подобную двоичному дереву поиска.