java中使用Iterator如何提高算法效率？

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

您必须添加更多条件。在这里，有三个选项：

abs(dif) <= k : 他们可以一起跳舞
dif > k : 连现在的男生（最小的）都比不上她，没人能和她跳舞，排除她
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;
            }
        }
    }
}

我使用获取索引来更灵活地处理列表内容

这是输出

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

java中使用Iterator如何提高算法效率？

How to improve the efficiency of the algorithm while using Iterator in java?

java

iterator

arraylist

processing-efficiency