Java比较无序的ArrayLists

Question

任何人都知道一种有效的方法来决定两个arraylists是否包含相同的值？

码:

ArrayList<String> dummy1= new ArrayList<String>();
list1.put("foo");
list1.put("baa");

ArrayList<String> dummy2= new ArrayList<String>();
list1.put("baa");
list1.put("foo");

dummy1 == dummy2

挑战在于,arraylists没有相同的价值秩序.

(foo, baa) == (foo, baa) // per definition :)

我需要得到这个

(foo, baa) == (baa, foo) // true

那么你的方法是什么？

Answer 1

先排序吧.

public  boolean equalLists(List<String> one, List<String> two){     
    if (one == null && two == null){
        return true;
    }

    if((one == null && two != null) 
      || one != null && two == null
      || one.size() != two.size()){
        return false;
    }

    //to avoid messing the order of the lists we will use a copy
    //as noted in comments by A. R. S.
    one = new ArrayList<String>(one); 
    two = new ArrayList<String>(two);   

    Collections.sort(one);
    Collections.sort(two);      
    return one.equals(two);
}

老实说,你应该检查你的数据结构决定.这似乎更像是一个问题.排序然后比较将采用O(nlog n),而HashSet比较将仅为O(n).

Answer 2

sort方法在O(n log n)中运行,但我们可以做得更好.首先执行空值和大小比较.然后使用a HashMap<String, Integer>并存储特定字符串的频率作为值.对其中一个列表执行此操作,然后迭代另一个列表并检查映射是否包含字符串并具有相同的频率.该方法是O(n).