请教一个算法问题，有两个数组A,B,判断A中是否至少有一个元素和B中元素相同

Question

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;namespace WindowsApplication6
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }
        string[] A ={ "X ", "Y ", "Z ", "W " };
        string[] B ={ "X ", "E ", "Z ", "U ", "V " }; 
        private void button1_Click(object sender, EventArgs e)
        {
            Dictionary<string, object> Test = new Dictionary<string, object>();
            foreach (string a in A)
            {
                if (!Test.ContainsKey(a))
                {
                    Test.Add(A, null);
                }
            }
            bool Return = false;
            foreach (string b in B)
            {
                if (Test.ContainsKey(b))
                {
                    MessageBox.Show("发现重复项：" + b);
                    Return = true;
                    break;
                }
            }            if (!Return)
            {
                MessageBox.Show("没有发现重复项" + b);
            }
        }
    }
}
我认为最快,最稳定的算法...
O(n)  n=A.len+b.len

Answer 1

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;namespace WindowsApplication6
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }
        string[] A ={ "X ", "Y ", "Z ", "W " };
        string[] B ={ "X ", "E ", "Z ", "U ", "V " }; 
        private void button1_Click(object sender, EventArgs e)
        {
            Dictionary<string, object> Test = new Dictionary<string, object>();
            foreach (string a in A)
            {
                if (!Test.ContainsKey(a))
                {
                    Test.Add(a, null);
                }
            }
            bool Return = false;
            foreach (string b in B)
            {
                if (Test.ContainsKey(b))
                {
                    MessageBox.Show("发现重复项：" + b);
                    Return = true;
                    break;
                }
            }            if (!Return)
            {
                MessageBox.Show("没有发现重复项");
            }
        }
    }
}
上楼的代码有点问题...欢迎拍砖

Answer 2

Re：楼主
　　你的直觉告诉你应该有更好的方法，确实如此！　　我们思考一下：
　　假设不是计算机来比较，而是人脑来比较，那么人脑会怎么思考呢？人脑首先会找各种窍门来排除不可能的元素，缩小查找范围吧！怎样让程序有接近人脑一样的思路，那就要靠咱们程序员的智慧了。我举例说明一下我要介绍的这种模拟人脑的思路，即模糊比较法：
假设本例中B组出现了非字母元素，例如中文字或者数字，即：
        string[] A ={ "X ", "Y ", "Z ", "W " };
       string[] B ={ "X ", "我 ", "9 ", "E ", "Z ", "U ", "V " }; 
我们人类一看就知道，A组的特征就是纯字母，B组的特征就是混合有非字母的元素，那我们大脑就会想，根本不用考虑这些非字母的元素，很自然的将其排除在视线之外。
根据人脑的这种思路编出的程序会是：第一遍先通过快速的模糊比较，剔除不可能的元素。第二遍再用楼主所说的二层嵌套循环，进行精确比较。这就是楼主苦求的更好的方法。这种方法在元素数量多的时候，效果尤其明显。我猜GOOGLE和BAIDU的搜索引擎也会这么做吧，如果不是，那他们大概需要升级了。模糊比较怎么做呢？
首先，模糊比较的方法可以不止一种，也就是说可以有多道工序按顺序叠加在一起，只要条件合理都可以写上。
假如楼主知道A、B来源都是纯字母，那就不必做上述的剔除非字母元素的程序，做了反而耽误时间。
假如楼主知道A组字符串长度范围，就可以把B组超长超短的字符串剔除。
还有种情况，假如楼主知道A、B组本身会出现大量重复的元素，就可以先做个剔除本组中重复元素的操作，这会为最后的二层嵌套循环节省时间。
如果元素数量很大的话，建议先做个排序再做剔除本组重复元素，这样剔除起来比较快，排序后的数组也会为最后的二层嵌套循环节省时间，甚至可以实现速度更快的二分法（好像也叫二叉树）。以上方法只是假设，在本例中并不适用，不过通过思考这些方法大家应该对模糊比较有个初步的认识了。
我这里提一个比较晦涩难懂的模糊比较法，抽取基因法，这在本例中是最有效的，我尽量说的详细点。这个方法中，元素都设定为char型变量，A组字母先用位操作计算出一个结果，即找出A组字母的基因，然后遍历一遍B组元素，把不含此基因的元素剔除掉。使用基因的方法有两种，&和|，我这里先详细介绍&方法，稍后会给出完整程序：先把A组所有字母按位进行&计算，即：
char result = 'X' & 'Y' & 'Z' & 'W';
我们都知道字母的ASCII范围：
'A'=65=01000001
'Z'=90=01011010
所以我们把A组所有元素按位&后结果存入result，观察result的后5位（前面的010是不会变的），看是否有1出现，如果后5位都是0，即result = 01000000 = 64，那我们就跳过这种模糊比较方案。如果某位是1，例如本例：
'X' = 01011000
'Y' = 01011001
'Z' = 01011010
'W' = 01010111
result = 01010000
就证明A组所有元素在该位都是1，我们就暂且称这个result为A组元素的基因。用这个基因与B组元素挨个&一次，如果结果与原先结果一致，就证明B组这个元素也包含相同的基因，我们保留，如果结果不一致，就剔除这个元素，因为这个元素某位是0，而A组所有元素该位都是1。第二种抽取基因的方法大家都已经想出来了吧，那就是用按位|的方法做，后边我不罗嗦了，给出程序大家讨论一下吧！
using System;namespace ConsoleApplication9
{
    class Program
    {
        static void Main(string[] args)
        {
            char[] A ={ 'X', 'Y', 'Z', 'W' };
            char[] B ={ 'X', 'E', 'Z', 'U', 'V' };            //用&方法算出基因，本例中会剔除B[]中的'E'
            char result = (char)0xffff;
            int point = 0;
            foreach (char a in A)
                result &= a;
            if (result != 64)
                foreach (char b in B)
                    if ((b & result) == result)
                        B[point++] = b;            //用|方法算出基因，本例中该基因不可用，跳过剔除
            foreach (char a in A)
                result |= a;
            if (result != 95)
            {
                int count = point;
                point = 0;
                for (int i = 0; i < count; i++)
                    if ((B[i] & result) == result)
                        B[point++] = B[i];
            }            //最后的嵌套循环
            for (int i = 0; i < point; i++)
                foreach (char a in A)
                    if (B[i] == a)
                    {
                        Console.WriteLine("Find out '{0}' in B!", a);
                        i = point;
                        break;
                    }
            Console.Read();
        }
    }
}
　　有人会问用|方法前result为什么不初始化成0，因为本例中不初始化不会出错，所以偷懒没写了。还有判断条件常数64和95给的太直接了吧，换一道题就不适用了。这确实是个问题，那完整的判断语句写法是什么呢？
　　楼下说吧！

Answer 3

刚才没仔细看
有些错误，我改正：using System;namespace ConsoleApplication9
{
    class Program
    {
        static void Main(string[] args)
        {
            char[] A ={ 'X', 'Y', 'Z', 'W' };
            char[] B ={ 'X', 'E', 'Z', 'U', 'V' };
            int point = B.Length;            // 用&方法算出基因，本例中会剔除B[]中的'E'
            char result = (char)0xffff;
            foreach (char a in A)
                result &= a;
            if (result != (result & ~0x1f))
            {
                point = 0;
                foreach (char b in B)
                    if ((b & result) == result)
                        B[point++] = b;
            }            // 用|方法算出基因，该基因不可用，跳过剔除
            // 这里省略了 result = 0;
            foreach (char a in A)
                result |= a;
            if (result != (result | 0x1f))
                for (int i = 0; i < point; i++)
                    if ((B[i] | result) != result)
                        B[i--] = B[--point];            // 最后的嵌套循环
            for (int i = 0; i < point; i++)
                foreach (char a in A)
                    if (B[i] == a)
                    {
                        Console.WriteLine("Find out '{0}' in B!", a);
                        i = point;
                        break;
                    }
            Console.Read();
        }
    }
}