java - 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 高度的女孩，因为我们已经对他们进行了排序，如果第一个男孩(较矮)不能与第一个女孩配对，那么肯定是第二个男孩(更长)也不能，如果我们与第一个女孩比较，我们会浪费时间。

我们可以通过两种选择解决这个问题，要么在前面的男孩停止后让迭代器从女孩开始(我不知道如何使用迭代器)，要么从数组列表中删除女孩一旦不满足条件，就让循环从第一个女孩开始(我试过了，但它给了我一个异常(exception))

如果可以就用这两种方法解决...

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;
            }
        }
    }
}

我使用 get index 来更灵活地处理列表内容

这是输出

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