判断两个数组中是否有相同的数字

http://blog.csdn.net/zzran/article/details/8201109

2012

首先要说声不好意思，因为这个题说的很模糊，但是也算是两个方向吧。也就是说，给定的两个数组是否有序，如果无序的话那么解决这个问题所用的时间复杂度就是nlog(n)，如果给定的两个数组有序，那么解决方法的时间复杂度会是O(n)。下面会给出两个解法。（假设数组是有序的，因为如果无序的话直接用快速排序或者堆排序在nlog(n)就可以解决）。

第一种方法，就是应用折半查找，依次从第一个数组中取出一个元素，到第二个数组中应用折半查找方法去寻找。这样一个循环内层加折半查找的嵌套，总得时间复杂度应该是mlog(n)(m,和n分别是两个数组的长度)。

第二种方法就是设定两个指针，分别指向第一个数组和第二个数组。取出指向的元素进行比较，如果ai<bj（因为数组是有序的），所以说明如果存在ak=bj，那么k应该在i之后，所以i得加1，如果i加1了以后，bj < a(i+1)，那么说明和a(i+1)相等的b数组中的元素要在bj之后，所以j要加1。依次类推，直到找到ai=bj，或者不存在，循环结束为止。这个算法的时间复杂度是Om+n).（m和n分别指两个数组的长度）。

[cpp] view plain copy

1. #include<stdio.h>  
2. int is_has_same_elem(int *a, int len_a, int *b, int len_b) {  
3.     int i;  
4.     int low, high, mid;  
5.     for(i=0; i < len_a; i++) {  
6.         low = 0;  
7.         high = len_b - 1;  
8.         while(low <= high) {  
9.             mid = low + (high - low) / 2;  
10.             if(a[i] == mid)  
11.                 return 1;  
12.             else if(a[i] > mid)  
13.                 low = mid + 1;  
14.             else  
15.                 high = mid - 1;  
16.         }  
17.     }  
18.     return 0;  
19. }  
20. int is_contain_same_elem(int *a, int len_a, int *b, int len_b) {  
21.     int count = 0;  
22.     int i, j;  
23.     i = j = 0;  
24.     while(i < len_a && j < len_b) {  
25.         if(a[i] == b[j])  
26.             return 1;  
27.         else if(a[i] < b[j])  
28.             i++;  
29.         else  
30.             j++;  
31.     }  
32.     return 0;  
33. }  
34. void main() {  
35.     int a[] = {1, 2, 3, 5, 6, 8, 10, 12};  
36.     int b[] = {4, 5, 7, 9, 11, 13};  
37.     int result;  
38.     result = is_has_same_elem(a, sizeof(a)/sizeof(int), b, sizeof(b)/sizeof(int));  
39.     if(result)  
40.         printf("ok\n");  
41.     else  
42.         printf("no\n");  
43.     result = is_contain_same_elem(a, sizeof(a)/sizeof(int), b, sizeof(b)/sizeof(int));  
44.     if(result)  
45.         printf("ok\n");  
46.     else  
47.         printf("no\n");  
48. }