|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101 |
using
System;using
System.Collections.Generic;using
System.Linq;using
System.Text;using
System.Text.RegularExpressions;namespace
ConsoleApplication1{ class
CompareArr { static
void Main(string[] args) { try { int[] srcArr1 = new
int[] { 2, 5, 6, 8, 10, 17, 29, 33, 43 };//假设数组长度为m int[] srcArr2 = new
int[] { 1, 3, 4, 7, 8, 13, 19, 20, 29, 39, 43 };//假设数组长度为n int[] resultArr = GetSameItem(srcArr1, srcArr2);//方法1 面试官要的答案，所谓的最多m+n次查找 //int[] resultArr = srcArr1.Where(t => srcArr2.Contains(t)).ToArray();//方法2：直接使用LINQ //int[] resultArr = GetSameItemByContains(srcArr1, srcArr2);//方法3 使用遍历加Contains方法 //其他方法：折半查找 if
(resultArr.Length > 0) { //Console.WriteLine(string.Format("srcArr1 {0}\nsrcArr2 {1}\n相同数字如下：", string.Join(",", srcArr1), string.Join(",", srcArr2))); Console.WriteLine("srcArr1 srcArr2 相同数字如下："); foreach
(int
item in
resultArr) { Console.WriteLine(item.ToString()); } } else { Console.WriteLine("无相同数字"); } Console.Read(); } catch
(Exception ex) { //记录异常 } } /// <summary> /// 查找两个有序数组中的相同数 /// 面试官要的答案，所谓的最多m+n次查找 /// </summary> /// <param name="srcArr1">有序数组1</param> /// <param name="srcArr2">有序数组2</param> /// <returns>数组，找到的相同数</returns> static
protected int[] GetSameItem(int[] srcArr1, int[] srcArr2) { List<int> resultArr = new
List<int>(); int
temIndex = 0; for
(int
i = 0; i < srcArr1.Length; i++) { for
(int
j = temIndex; j < srcArr2.Length; j++) { if
(srcArr1[i] > srcArr2[j]) { continue; } else
if (srcArr1[i] < srcArr2[j]) { temIndex = j; break; } else { temIndex = j + 1; resultArr.Add(srcArr1[i]); } } } return
resultArr.ToArray(); } /// <summary> /// 查找两个有序数组中的相同数 /// 使用遍历加Contains方法 /// </summary> /// <param name="srcArr1">有序数组1</param> /// <param name="srcArr2">有序数组2</param> /// <returns>数组，找到的相同数</returns> static
protected int[] GetSameItemByContains(int[] srcArr1, int[] srcArr2) { List<int> resultArr = new
List<int>(); for
(int
i = 0; i < srcArr1.Length; i++) { if
(srcArr2.Contains<int>(srcArr1[i])) { resultArr.Add(srcArr1[i]); } } return
resultArr.ToArray(); } }} |
其他人的分析总结：http://blog.csdn.net/insistgogo/article/details/9228015
http://hi.baidu.com/algorithms/item/186115ec71d696abc00d757a
原文：http://www.cnblogs.com/xuezhizhang/p/3557149.html