java中使用Iterator时如何提高算法的效率? [英] How to improve the efficiency of the algorithm while using Iterator in java?

问题描述

问题来了:有N个男孩和N个女孩.只有男孩和女孩可以组成舞对(即不允许同性舞对).配对的唯一其他条件是它们的绝对高度差应小于或等于K.

This is the question: There are N boys and N girls. Only a boy and a girl can form a dancing pair (i.e. no same sex dancing pairs are allowed). The only other condition in making pairs is that their absolute difference in height should be less than or equal to K.

找出可以形成的最大配对数，以便每个人都有一个独特的伙伴.

Find the maximum number of pairs that can be formed so that everyone has a unique partner.

我想改进我的算法以减少时间..先看代码:

I want to improve my algorithm to take less time.. first see the code:

    //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);

这段代码的输出是:

如您所见，此算法效率低下，因为我们不需要开始比较第二个男孩的第一个女孩的身高，我们应该去比较我们配对的前一个女孩之后的女孩.

As you see this algorithm inefficient since we don't need to start comparing the height from the first girl for the second boy, we should go to the girl which come after the previous girl we took as pair.

例如:在身高22的男孩中，算法必须开始比较男孩的身高和身高14的女孩，因为我们已经对他们进行了排序，如果第一个男孩(更矮的)不能和第一个女孩配对，那么肯定是第二个男孩(更长)也不能，如果我们和第一个女孩比较，我们浪费时间.

For example: in the boy with 22 height, the algorithm must start comparing the boys'height with the girl with 14 height, because we already sort them, if the first boy (shorter) cant make a pair with the first girl so definitely the second boy (longer) cant also, we waste the time if we compare from the first girl.

我们可以通过两种选择来解决这个问题，要么在前一个男孩停止后让迭代器从女孩开始(我不知道如何用迭代器来做)，或者通过从数组列表中移除女孩一次，如果它不满足条件，让循环从第一个女孩开始(我试过这个，但它给了我一个例外)

We can solve this problem by two choices, either by making the iterator start with the girl after the previous boy has been stopped (i don't know how to do it with iterator), or by removing the girl from the arraylist once if it's not satisfy the condition and let the loop start with first girl (i tried this but it gives me an exception)

如果可以的话，通过这两种方法解决它...

Solve it by these two ways if you can...

推荐答案

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

You have to add more conditions. Here it is, there are three options :

• 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 来提高列表内容的可操作性

I used get index for more maniability on lists content

这是输出

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时如何提高算法的效率?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！