Алгоритм, чтобы сказать, имеют ли два массива идентичных участников

Question

Алгоритм, чтобы сказать, имеют ли два массива идентичных участников

Каков лучший алгоритм для сравнения двух массивов, чтобы видеть, есть ли у них те же участники?

Предположите, что нет никаких дубликатов, участники могут быть в любом порядке, и что ни один не отсортирован.

compare(
    [a, b, c, d],
    [b, a, d, c]
) ==> true

compare(
    [a, b, e],
    [a, b, c]
) ==> false

compare(
    [a, b, c],
    [a, b]
) ==> false

27

algorithm

задан nickf 29 October 2008 в 01:33

1 ответ

Другие вопросы по тегам:

algorithm

Похожие вопросы:

score 0 · Answer 1

Вот еще один вариант, дайте мне знать, что вы думаете. Это должно быть T (n) = 2n * log2n -> O (nLogn) в худший случай.

private boolean compare(List listA, List listB){
    if (listA.size()==0||listA.size()==0) return true;
    List runner = new ArrayList();
    List maxList = listA.size()>listB.size()?listA:listB;
    List minList = listA.size()>listB.size()?listB:listA;
    int macthes = 0;
    List nextList = null;;
    int maxLength = maxList.size();
    for(int i=0;i<maxLength;i++){
        for (int j=0;j<2;j++) {
            nextList = (nextList==null)?maxList:(maxList==nextList)?minList:maList;
            if (i<= nextList.size()) {
                MatchingItem nextItem =new MatchingItem(nextList.get(i),nextList)
                int position = runner.indexOf(nextItem);
                if (position <0){
                    runner.add(nextItem);
                }else{
                    MatchingItem itemInBag = runner.get(position);
                    if (itemInBag.getList != nextList)   matches++;
                    runner.remove(position);
                }
            }
        }
    }
    return maxLength==macthes;
}

public Class MatchingItem{
private Object item;
private List itemList;
public MatchingItem(Object item,List itemList){
    this.item=item
    this.itemList = itemList
}
public boolean equals(object other){
    MatchingItem otheritem = (MatchingItem)other;
    return otheritem.item.equals(this.item) and otheritem.itemlist!=this.itemlist
}

public Object getItem(){ return this.item}
public Object getList(){ return this.itemList}

}