你能帮我离开这里吗 [英] Can you please help me out of here

问题描述

大家好，

假设您需要确定两个ArrayList是否相等，除了您不在乎两个列表中元素的顺序是否相同.以下是据称可以解决此问题的一种方法:

Hi all,

Suppose you need to determine whether two ArrayLists are equal except you don''t care whether the orders of the elements in the two lists are the same. Here is one method that purportedly solves this problem:

    public boolean specialArrayListEquals(ArrayList a1, ArrayList a2){
    	boolean result = true;
    	a1 = new ArrayList(a1);  //create a clone of a1
    	a2 = new ArrayList(a2);  //create a clone of a2
if(a1.size() == a2.size()) {
    		for(int i = 0; ((i < a1.size()) && (result == true)); i++){
    			Object o = a1.get(i);
    			result = a2.contains(o);
    			if(result){ // remove the equal elements from both
    				a1.remove(o);
    				a2.remove(o);
    			}
    		}
    	}
    	return result;
    }

调试该代码，列出使该代码难以理解的所有内容，然后为该问题提供一个优雅的解决方案.如果您知道每个ArrayList中没有重复的元素(即，没有两个相等的元素)，您能否提出一个更优雅的解决方案?

谢谢
sujan.

Debug this code, list everything you can think of that makes this code inelegant, and then come up with an elegant solution to the problem. Can you come up with an even more elegant solution if you know that there are no duplicate elements (that is, no two equal elements) in each ArrayList?

Thanks
sujan.

推荐答案

显示的解决方案也无效，因为方法remove和contain以O(n)的速度工作. (要了解大O表示法"，请参见 http://en.wikipedia.org/wiki/Big_O_notation [ ^ ].)

速度方面的考虑和无重复的限制建议使用java.util.Hashtable，请参见 http://download.oracle.com/javase/1.4.2/docs/api/java/util/Hashtable.html [

The solution you show is also ineffective as the methods remove and contain works at the speed of O(n). (For understanding "Big O Notation", see http://en.wikipedia.org/wiki/Big_O_notation[^].)

Speed considerations and the no-duplicate constrain suggest the use of java.util.Hashtable, see http://download.oracle.com/javase/1.4.2/docs/api/java/util/Hashtable.html[^] at the expense of some memory overhead. For big collections, this class provides the speed about O(1) (no dependency on the size of collection, constant search time for big collections).

You can populate an instance of hash table from one list and try to find the elements of another list one by one. The rest of this algorithm is simple, so I would leave to for your home exercise :-).

—SA

这篇关于你能帮我离开这里吗的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！