大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > C#技巧 > 有两数组A、B,长度分别为m、n。用不超过m+n的比较次数找到两个数组中的相同元素

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

关键词:两个数组中的相同元素  阅读(558) 赞(20)

[摘要]本文是对有两数组A、B,长度分别为m、n。用不超过m+n的比较次数找到两个数组中的相同元素的讲解,对学习C#编程技术有所帮助,与大家分享。

今天碰到一道笔试题:有两数组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。



相关评论