Как повысить эффективность алгоритма при использовании Iterator в java?

Question

Это вопрос: Есть N мальчиков и N девочек. Только мальчик и девочка могут сформировать танцевальную пару (т. Е. Не разрешены пары одного пола). Единственное другое условие при создании пар состоит в том, что их абсолютная разница в высоте должна быть меньше или равна K.

Найти максимальное количество пар, которые могут быть сформированы так, чтобы у каждого был уникальный партнер.

Я хочу улучшить свой алгоритм, чтобы занять меньше времени .. сначала увидеть код:

//k is the maximum difference between pairs 
    int k = 5; 
    ArrayList<Integer> ArrBoys = new ArrayList<>(Arrays.asList(new Integer[]{28, 16, 22})); 
    ArrayList<Integer> ArrGirls = new ArrayList<>(Arrays.asList(new Integer[]{13, 10, 14})); 

    //sorting all arrays 
    Collections.sort(ArrBoys); 
    Collections.sort(ArrGirls); 

    System.out.println("After Sorting"); 

    //printing arrays after sorting 
    for (Integer ArrBoy : ArrBoys) { 
     System.out.print(ArrBoy + " "); 
    } 
    System.out.println(""); 
    for (Integer ArrGirl : ArrGirls) { 
     System.out.print(ArrGirl + " "); 
    } 
    System.out.println(""); 

    //algorithm used to find the number of pairs 
    int count = 0; 
    for (Iterator<Integer> iteB = ArrBoys.iterator(); iteB.hasNext();) { 
     Integer ArrBoy = iteB.next(); 
     for (Iterator<Integer> iteG = ArrGirls.iterator(); iteG.hasNext();) { 
      { 
       Integer ArrGirl = iteG.next(); 
       int dif = (int) Math.abs(ArrBoy - ArrGirl); 
       if (dif <= k) { 
        System.out.println("we took " + ArrBoy + " from boys with " 
          + ArrGirl + " from girls, thier dif < " + k); 
        ArrBoys.remove(ArrBoy); 
        ArrGirls.remove(ArrGirl); 
        iteB = ArrBoys.iterator(); 
        count++; 
        break; 
       } else { 
        System.out.println("we try " + ArrBoy + " from boys with " + ArrGirl + " from grils but thier dif > " + (int) k); 
        //ArrGirls.remove(ArrGirl);     
       } 
      } 

     } 
    } 
    System.out.println("the number of pairs we can take is "+count); 

выход этого кода:

Как вы видите этот алгоритм неэффективен, так как нам не нужно начинать сравнивать высоту с первой девушкой для второго мальчика, мы должны пойти к девушке, которая придет после предыдущей девушки, которую мы взяли в качестве пары.

Например: в мальчике с высотой 22, алгоритм должен начать сравнивать мальчиков с девушкой с 14-ю высотами, потому что мы уже сортируем их, если первый мальчик (короче) не может создать пару с первая девушка, так определенно, второй мальчик (дольше) тоже не может, мы теряем время, если сравним с первой девушкой.

Мы можем решить эту проблему двумя вариантами: либо начать итератор с девушкой после того, как предыдущий мальчик был остановлен (я не знаю, как это сделать с помощью итератора), либо удалив девушку из ArrayList один раз, если он не удовлетворяет условию и пусть петля начать с первой девушкой (я попробовал это, но это дает мне исключение)

Решить ее этими двумя способами, если вы можете ...

Answer 1

вы должны добавьте больше условий. Здесь есть три варианта:

• абс (диф) < = к: они могут танцевать вместе
• диф> к: даже текущий мальчик (самый маленький) слишком высок для нее, не один может танцевать с ней, исключить ее
• DIF < -k: первая девушка слишком высока для него, исключить его

Вот код:

int count = 0; 
int gLimit = 0; 
for (int b = 0; b<ArrBoys.size();b++) { 
    if(gLimit == ArrGirls.size()) { 
     System.out.println("no more girl for boy " + ArrBoys.get(b)); 
    } 
    for (int g = gLimit; g<ArrGirls.size();g++) { 
     { 

      int dif = ArrBoys.get(b) - ArrGirls.get(g); 
      if (Math.abs(dif) <= k) { 
       System.out.println("we took " + ArrBoys.get(b) + " from boys with " 
         + ArrGirls.get(g) + " from girls, thier dif < " + k); 
       gLimit++; 
       count++; 
       break; 
      } else if (dif > k) { 
       System.out.println("we try " + ArrBoys.get(b) + " from boys with " + ArrGirls.get(g) + " from grils but thier dif > " + (int) k + ", girl too small, excluded"); 
       gLimit++; 
      } else if (dif < -k) { 
       System.out.println("we try " + ArrBoys.get(b) + " from boys with " + ArrGirls.get(g) + " from grils but thier dif > " + (int) k + ", boy too small, excluded"); 
       break; 
      } 
     } 
    } 
} 

Я использовал индекс Получите более maniability по содержанию списков

Вот Ouput

After Sorting 
16 22 28 
10 13 14 
we try 16 from boys with 10 from grils but thier dif > 5, girl too small, excluded 
we took 16 from boys with 13 from girls, thier dif < 5 
we try 22 from boys with 14 from grils but thier dif > 5, girl too small, excluded 
no more girl for boy 28 
the number of pairs we can take is 1