求一个简单的算法

Question

有N个数组 假设 20<N<500
每个数组有M个 对象假设 10<M<5000
找出这N个数组重复的对象
求一个简捷的算法.无所谓什么语言,只要提供一个思路就可以了

Answer 1

如果你的内存足够的话, 那么使用hash表最快的.比如: 假设你有N个数组, 叫arr1,arr2...arrNfor(int i=0;i< arr1.length;i++)
{
    hash[arr1[i]] = hash[arr1[i]] | 1<<1;
}for(int i=0;i< arr2.length;i++)
{
    hash[arr2[i]] = hash[arr2[i]] | 1<<2;
}
...最后只需要查看一下hash表, 找出value值为2^n就可以了.这个复杂度为O(N).
如果你内存不是很够, 那么先排序, 然后遍历一遍也可以了. while(i< arr1.length && j< arr2.length)
{
     if(arr1[i]< arr2[j])
     {
         i++;
     }
     ...
}
考虑先将两个最小的数组排序, 并遍历, 得出共同数组, 共同数组再和第三小的数组排序并遍历. 以此和更大的数组比较.你用快排, 这样算法是O(nlogN). 但可以节约一些内存.
在实际工作中, 你用Linux下的diff命令, 或者windows下的fc命令, 简单几行脚本就能实现你的要求.

Answer 2

Step 1:
write a class to wrap such objects, like this
class Wrapper
{
   object obj;
   int arrayIndex; // Store which array such object belongs to
}Step 2:
Define its comparing rules by implementing IComparable<T> interface.
Comparing Rule: Compare by Wrapper.obj.Step 3:
Read from those arrays, make the wrapper for them. Store those objects in a ArrayList.Step 4:
Sort the ArrayList. ArrayList.Sort().Step 5:
Count each object one by one. 
If the number of certain object is  >= N, Then check whether these objects belongs to each array by checking those Wrapper's arrayIndex.
If so, then it is target you want to find.

Answer 3

Sorry, my system has no chinese input. Am installing one.

Answer 4

you are ox man !