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

时间:2022-12-31 00:03:00
 

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

分类: 面试题 算法 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)两个数组的元素分布不均匀