首页 > 代码库 > 有两数组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。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。