hash table. Or you can sort it and use the same strategy as merge in merge sort. if there is k array, use the same strategy in k way merge, use an heap to hold head elements.
a*a
5 楼
personal的有这个?
【在 n*******a 的大作中提到】 : Amex Biz Gold有什么特有的周年优惠吗,像personal的$200 airline之类的。谢谢!
【在 y*****n 的大作中提到】 : hash table. : Or you can sort it and use the same strategy as merge in merge sort. : if there is k array, use the same strategy in k way merge, use an heap to : hold head elements.
put all elements of one array into an hashtable, then scan another array to check if current element is in hashtable, if yes then current element is belong to intersection. for union, just use hashset, put all elements in two arrays in hashset, then the elements in hashset is what you want. hashset will not permit repeated elements(at least in java= =)
【在 y*****n 的大作中提到】 : put all elements of one array into an hashtable, then scan another array to : check if current element is in hashtable, if yes then current element is : belong to intersection. : for union, just use hashset, put all elements in two arrays in hashset, then : the elements in hashset is what you want. : hashset will not permit repeated elements(at least in java= =)
It doesn't matter what you put in this case. You can use HashSet, you don't care about the value, you only care the existence of the key. Java Hashset internally is backed by a hashmap, it stores the "this" as value. /** * Adds the specified object to this HashSet. * * @param object * the object to add * @return true when this HashSet did not already contain the object, false * otherwise */ @Override public boolean add(E object) { return backingMap.put(object, this) == null; } For the hashvalue of the key, it's used to determine the bucket of the hashtable. Java HashMap will do some processing on the hashvalue to avoid conflicting. static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } You can look at Java source code for more details: http://hg.openjdk.java.net/jdk6/jdk6/jdk/file/a42d6999734b/src/