给定两个排好序的数组,怎样高效地判断这两个数组中是否存在相同的数字?不妨设函数原型为: bool findCommon(int a[],int size_a,int b[],int size_b); 撰写源码并说明时间复杂度。
排好序应该是升序吧,复杂度O(size_a+size_b) boolean findCommon(int a[],int size_a,int b[],int size_b){ boolean res=false; if(size_a<=0||size_b<=0) return res; int i=0,j=0; while(i<size_a&&j<size_b) { if(a[i]==b[j]){ res=true; break; } if(a[i]<b[j]) i++; else j++; } return res; }