] 两个有序非重数组，如果查找数组之间的重复元素 (未完成)

 

[置顶] 两个有序非重数组，如果查找数组之间的重复元素 (未完成)

分类： 面试题 算法2013-07-02 20:09 34人阅读 评论(0) 收藏 举报

目录(?)[+]

引言：

最近求实习未遂，在离开实验室前，把在实验室写的一些程序整理下。

题目描述：

两个元素递增且不重复的数组A和B，查找数组之间的重复元素，并放到其他数组C中。

举例：

A数组 : 1、3、5、7、10

B数组 : 2、3、4、5、6

程序输出C数组：3、5。

注意，这里的方法都不涉及哈希。

方法：

方法 1：二路归并

思路：直接对两个数组进行归并，找出相等元素

具体思路：分别设两个游标 nCurA 和 nCurB，比较游标指向的元素，谁小谁往前走。直到任意一个游标越界为止。

如果 A[nCurA] > B[nCurB] ,则 nCurB++

如果 A[nCurA] < B[nCurB],则 nCurA++

如果 A[nCurA] = B[nCurB] ,则 存入数组C中，并且两个游标均往前移动

代码：

[cpp] view plaincopyprint?

1. void FindSameNum_Merge()  
2. {  
3.     int nCurA = 0;  
4.     int nCurB = 0;  
5.     int nSameCount = 0;  
6.     while (nCurA < nLenA && nCurB < nLenB)  
7.     {  
8.         if (A[nCurA] > B[nCurB])  
9.         {  
10.             nCurB++;  
11.         }  
12.         else if (A[nCurA] < B[nCurB])  
13.         {  
14.             nCurA++;  
15.         }  
16.         else  
17.         {  
18.             C[nSameCount] = A[nCurA];  
19.             nCurB++;  
20.             nCurA++;  
21.         }  
22.     }     
23. }  

时间复杂度分析

假设数组A的长度为n，数组B的长度为m，则时间复杂度为O（m+n）

使用场合：

不要觉得这个方法笨啊，在两个数组中的元素分布均匀且长度相差不大时，与其他算法相比，还是很快的。

方法 2：短数组（固定） + 二分查找 

思想：用短数组的数据到其他数组进行二分查找，这个短数组是在查找之前确定，而且在程序执行中一直不变。

具体思路：

（1）根据数组A和B中元素长度，确定一个长度最短的数组，假设为B。

（2）每次从B数组中拿出一个数据num，去A数组中二分查找：

如果：num在A数组中存在，则存储到C数组中，两个游标均往前走一个

如果：num在A数组中不存在，则从B数组中取出下一个元素，再去A数组中二分查找

注意：在A中二分查找时，二分查找的起始位置可以根据上次二分查找位置确定，这样就不用每次都从头开始查找了。

代码：

[cpp] view plaincopyprint?

1. void FindSameNum_BinSearch_Base()  
2. {  
3.     int nCurA = 0;  
4.     int nCurB = 0;  
5.     int nSameCount = 0;  
6.     int low = 0;  
7.     bool isFind = false;  
8.     while (nCurA < nLenA && nCurB < nLenB)//已知B数组短  
9.     {  
10.         nCurA = BinSearch(A,B[nCurB],nCurA,nLenA - 1,isFind);//拿B中的一个元素去A数组中查找  
11.   
12.         if (isFind)  
13.         {  
14.             C[nSameCount++] = B[nCurB];  
15.         }  
16.         nCurB++;  
17.     }  
18. }  
19.   
20. int BinSearch(int arr[],int key,int low,int high,bool& isFind)  
21. {  
22.     int mid = 0;  
23.     while (low <= high)  
24.     {  
25.         mid = (low + high)/2;  
26.   
27.         if (key >= arr[mid])  
28.         {  
29.             low = mid + 1;  
30.         }  
31.         else  
32.         {  
33.             high = mid -1;  
34.         }  
35.     }  
36.     /*如果存在key，则low指向key， 
37.     不存在key，则low指向第一个比key大的数， 
38.     比key大的数不存在，则越界*/  
39.     if (high > -1 && arr[high] == key)  
40.     {  
41.         isFind = true;  
42.         return low;  
43.     }  
44.     else  
45.     {  
46.         isFind = false;  
47.         return low;  
48.     }  
49. }  

时间复杂度分析

。。。。未分析

使用场合：

（1）使用于两个数组长度差比较大

（2）两个数组的元素分布不均匀

评价：这个算法还不算最快，还可以改进。

方法 3：短数组（不固定） + 二分查找 

思想：用短数组的数据到其他数组进行二分查找，这个短数组不是固定的，而是一直在变化的。

怎么确定短数组呢：在每次执行完一次查找后，都根据两个数组待查找的元素个数，选择一个短数组。

具体思路：

（1）根据数组A和B中元素长度，确定一个长度最短的数组ShorstArr。

（2）每次从ShorstArr数组中拿出一个数据num，去另外一个数组中二分查找，思路与上个方法一样。

（3）在执行完一次查找后，重新计算两个数组待处理元素的个数，选择一个短数组ShorstArr

（4）循环执行步骤（3）和步骤（4），直到某一个数组处理完毕。

注意：

每次执行二分查找时，二分查找的起始位置都是指向目前待处理的元素，不能从数组第一个元素开始查找

代码：

[cpp] view plaincopyprint?

1. void FindSameNum_BinSearch_OPT()  
2. {  
3.     int nCurA = 0;  
4.     int nCurB = 0;  
5.     int nSameCount = 0;  
6.     int low = 0;  
7.     bool isFind = false;  
8.     while (nCurA < nLenA && nCurB < nLenB)  
9.     {  
10.         if (nLenA - nCurA <= nLenB - nCurB)//处理A数组  
11.         {  
12.             nCurB = BinSearch(B,A[nCurA],nCurB,nLenB - 1,isFind);//拿A中的一个元素去A数组中查找  
13.   
14.             if (isFind)  
15.             {  
16.                 C[nSameCount++] = A[nCurA];  
17.             }  
18.             nCurA++;   
19.   
20.         }  
21.         else //处理B数组  
22.         {  
23.             nCurA = BinSearch(A,B[nCurB],nCurA,nLenA - 1,isFind);//拿B中的一个元素去A数组中查找  
24.   
25.             if (isFind)  
26.             {  
27.                 C[nSameCount++] = B[nCurB];  
28.             }  
29.             nCurB++;  
30.         }  
31.     }  
32. }  
33.   
34. int BinSearch(int arr[],int key,int low,int high,bool& isFind)  
35. {  
36.     int mid = 0;  
37.     while (low <= high)  
38.     {  
39.         mid = (low + high)/2;  
40.   
41.         if (key >= arr[mid])  
42.         {  
43.             low = mid + 1;  
44.         }  
45.         else  
46.         {  
47.             high = mid -1;  
48.         }  
49.     }  
50.     /*如果存在key，则low指向key， 
51.     不存在key，则low指向第一个比key大的数， 
52.     比key大的数不存在，则越界*/  
53.     if (high > -1 && arr[high] == key)  
54.     {  
55.         isFind = true;  
56.         return low;  
57.     }  
58.     else  
59.     {  
60.         isFind = false;  
61.         return low;  
62.     }  
63. }  

时间复杂度分析

。。。。未分析

使用场合：

（1）使用于两个数组长度差比较大

（2）两个数组的元素分布不均匀

评价：这个算法看着挺有道理，但是发现实际效果不咋好啊。

方法 4：最大值 + 二分查找 

思想：每次都从两个数组中找到一个最大值，之后使用这个最大值到另一个数组进行二分查找。

具体思路：

（1）根据数组A和B中元素，确定一个最大值 nMaxNum。

（2）使用这个最大值 nMaxNum，到非最大值所在数组进行二分查找：

如果、在另外一个数组也找到该值 nMaxNum，则两个数组的游标均往前走一个，并存到数组C中

如果、在另外一个数组没找到该值 nMaxNum，则两个数组游标均指向下一个元素

（3）从游标位置继续循环执行步骤（1）和（2），直到任意一个数组处理完毕为止。

代码：

[cpp] view plaincopyprint?

1. void FindSameNum_MaxNumBinSearch()  
2. {  
3.     int nCurA = 0;  
4.     int nCurB = 0;  
5.     int nSameCount = 0;  
6.     int nMaxNum = -1;  
7.     bool IsSameNum = false;  
8.     bool isFind = false;  
9.   
10.     while (nCurA < nLenA && nCurB < nLenB)  
11.     {  
12.         nMaxNum = GenMaxNum(nCurA,nCurB,IsSameNum);  
13.         if (IsSameNum)  
14.         {  
15.             C[nSameCount++] = A[nCurA];  
16.             nCurA++;  
17.             nCurB++;  
18.         }  
19.         else  
20.         {  
21.             if (A[nCurA] == nMaxNum) //到B数组中找最大值  
22.             {  
23.                 nCurB = BinSearch(B,nMaxNum,nCurB,nLenB - 1,isFind);  
24.   
25.                 if (isFind)  
26.                 {  
27.                     C[nSameCount++] = nMaxNum;  
28.                 }  
29.                 nCurA++;  
30.             }  
31.             else  //到A数组中找最大值  
32.             {  
33.                 nCurA = BinSearch(A,nMaxNum,nCurA,nLenA - 1,isFind);  
34.   
35.                 if (isFind)  
36.                 {  
37.                     C[nSameCount++] = nMaxNum;  
38.                 }  
39.                 nCurB++;  
40.             }  
41.         }  
42.     }  
43. }  
44.   
45. int GenMaxNum(int nCurA,int nCurB,bool& IsSameNum)  
46. {  
47.     if (A[nCurA] > B[nCurB])  
48.     {  
49.         IsSameNum = false;  
50.         return A[nCurA];  
51.     }  
52.     else if (A[nCurA] < B[nCurB])  
53.     {  
54.         IsSameNum = false;  
55.         return B[nCurB];  
56.     }  
57.     else  
58.     {  
59.         IsSameNum = true;  
60.         return A[nCurA];  
61.     }  
62. }  
63.   
64. int BinSearch(int arr[],int key,int low,int high,bool& isFind)  
65. {  
66.     int mid = 0;  
67.     while (low <= high)  
68.     {  
69.         mid = (low + high)/2;  
70.   
71.         if (key >= arr[mid])  
72.         {  
73.             low = mid + 1;  
74.         }  
75.         else  
76.         {  
77.             high = mid -1;  
78.         }  
79.     }  
80.     /*如果存在key，则low指向key， 
81.     不存在key，则low指向第一个比key大的数， 
82.     比key大的数不存在，则越界*/  
83.     if (high > -1 && arr[high] == key)  
84.     {  
85.         isFind = true;  
86.         return low;  
87.     }  
88.     else  
89.     {  
90.         isFind = false;  
91.         return low;  
92.     }  
93. }  

时间复杂度分析

。。。。未分析

使用场合：

这种方法在绝大部分都是比前几个算法的快的，尤其是在下面两个情况的任一情况时，效果更明显。

（1）适用于两个数组长度差比较大

（2）两个数组的元素分布不均匀

分享到： 

上一篇：每日一题(21) - 编写memmove 函