数组比较算法

Question

原来有个送分帖子，单没有人回答哈
http://topic.csdn.net/u/20091119/15/ff77ed42-dcf8-4fff-8e53-f8e6b30fe40a.html题目：怎么快速找出2个数组中的相同项，数组可能很大

Answer 1

有空间限制么？没有的话设第三个数组大小一样大的数组bool[] flag，全部初始化false。设原有数组为int[] a; int[] b;
遍历数组a，赋值flag[a[i]]=true;
遍历数组b，检查如果flag[b[i]]为true，显然数组a中有相同的数。

Answer 2

错了，数据bool[] flag的大小是尽可能大，不是和两上数组相同大小

Answer 3

代码实现也不多            int[] a = new int[10000];
            int[] b = new int[10000];
            bool[] flag = new bool[MAX];            for (int i = 0; i < MAX; i++)
                flag[i] = false;            for (int i = 0; i < 10000; i++)
                flag[a[i]] = true;            for (int i = 0; i < 10000; i++)
                if (flag[b[i]])
                    Console.WriteLine(b[i]); //输出相同元素

Answer 4

我当时给的答案就是用hashtable

Answer 5

string[] arry1 = new string[]{ "aa", "12", "bb" };
string[] arry2 = new string[]{ "bb", "16", "ll", "ds" };foreach (string str in arry1)
{
    if (Array.IndexOf(arry2, str) > -1)
    {
        MessageBox.Show(str.ToString());
    }
}

Answer 6

比较O(n*n)和O(n)的效率，用不着直觉吧

Answer 7

空间换时间是最好的方法，
hashtable应该可以的

Answer 8

提供四种方法，第四种是C#3.0以上才有的linq         static void Main(string[] args)
        {
            int[] arrA = new int[short.MaxValue];
            int[] arrB = new int[short.MaxValue];
            Random r = new Random(Environment.TickCount);
            for (int i = 0; i < short.MaxValue; i++)
            {
                arrA[i] = r.Next(0, int.MaxValue);
                arrB[i] = r.Next(0, int.MaxValue);
            }
            //以上是构建数据
            int tick = Environment.TickCount;
            GetSameItem1(arrA, arrB);
            Console.WriteLine(Environment.TickCount - tick);
            tick = Environment.TickCount;
            GetSameItem2(arrA, arrB);
            Console.WriteLine(Environment.TickCount - tick);
            tick = Environment.TickCount;
            GetSameItem3(arrA, arrB);
            Console.WriteLine(Environment.TickCount - tick);
            tick = Environment.TickCount;
            GetSameItem4(arrA, arrB);
            Console.WriteLine(Environment.TickCount - tick);
        }        static List<int> GetSameItem1(int[] arrA, int[] arrB)
        {
            List<int> list = new List<int>();
            foreach (int i in arrA)
                if (Array.IndexOf(arrB, i) > -1)
                    list.Add(i);
            return list;
        }        static List<int> GetSameItem2(int[] arrA, int[] arrB)
        {
            List<int> list = new List<int>(arrA);
            foreach (int i in arrB)
                list.Remove(i);
            return list;
        }        static List<int> GetSameItem3(int[] arrA, int[] arrB)
        {
            Dictionary<int, bool> dic = new Dictionary<int, bool>();
            List<int> list = new List<int>();
            foreach (int i in arrA)
            {
                if (dic.ContainsKey(i))
                {
                    dic[i] = true;
                    list.Add(i);
                }
                else
                    dic.Add(i, false);
            }
            foreach (int i in arrB)
            {
                if (dic.ContainsKey(i))
                {
                    dic[i] = true;
                    list.Add(i);
                }
                else
                    dic.Add(i, false);
            }
            return list;
        }        static List<int> GetSameItem4(int[] arrA, int[] arrB)
        {
            return arrA.Intersect(arrB).ToList();
        }

Answer 9

第三个方法改改：        static List<int> GetSameItem3(int[] arrA, int[] arrB)
        {
            Dictionary<int, bool> dic = new Dictionary<int, bool>();
            List<int> list = new List<int>();
            foreach (int i in arrA)
            {
                if (!dic.ContainsKey(i))
                    dic.Add(i, false);
            }
            foreach (int i in arrB)
            {
                if (dic.ContainsKey(i))
                {
                    dic[i] = true;
                    list.Add(i);
                }
                else
                    dic.Add(i, false);
            }
            return list;
        }

Answer 10

用循环，我觉得最快了，再就IndexOf就行了，这样多点也应该没问题吧挺好的