首页 > 代码库 > 有两数组A、B,长度分别为m、n。用不超过m+n的比较次数找到两个数组中的相同元素

有两数组A、B,长度分别为m、n。用不超过m+n的比较次数找到两个数组中的相同元素

今天碰到一道笔试题:有两数组A、B,长度分别为m、n。用不超过m+n的比较次数找到两个数组中的相同元素。当时没做出来,我现在给出C#版本,算是弥补一点遗憾。

using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace SortAB{    class Program    {        static void Main(string[] args)        {            int[] A = RandomIntArray(10); // m = 10            int[] B = RandomIntArray(5);  // n = 5                        // 输出两个数组            Console.Write("数组A:");            foreach(int m in A)                Console.Write("{0} ", m.ToString());            Console.Write("\n数组B:");            foreach (int n in B)                Console.Write("{0} ", n.ToString());            // 找出数组中相同的元素            StringBuilder list = new StringBuilder();            foreach (int m in A)            {                int getInt = find(m, B);                if (getInt != -1)                    list.Append(B[getInt]);            }            Console.WriteLine();             Console.Write("两个数组中重复的元素有:{0} ", list);            // 用两个数组的交集,来验证            IEnumerable<int> intersect = A.Intersect(B);            Console.Write("\n两个数组的交集:");            foreach (int vars in intersect)                Console.Write("{0} ", vars);            Console.ReadLine();        }        // 二分查找。N 必须为有序数组,否则会出错        public static int find(int key, int[] N)        {            int lb = 0;            int ub = N.Length - 1;            int temp;            while(true)            {                temp = (lb + ub)/2;                if(N[temp] == key)    return temp;                else if(lb > ub)      return -1;                else                {                    if(N[temp] < key)    lb = temp+1;                    else                   ub = temp-1;                }            }        }        public static int[] RandomIntArray(int count)        {            int[] array = new int[count];            Random r = new Random(unchecked((int)DateTime.Now.Ticks));             for (int i = 0; i < count; i++)            {                array[i] = r.Next(100);            }            return array;        }    }    }

不过,我现在仍是疑惑:比较次数有可能会大于m+n。