题目:
数组A中任意两个相邻元素大小相差1,现给定这样的数组A和目标整数t,找出t在数组A中的位置。
如数组:[1,2,3,4,3,4,5,6,5],找到4在数组中的位置。
思路:
很明显,在数组中寻找某个数的复杂度为O(n),但在某些特殊数组中,可以通过寻找规律来减少比较次数。
上述数组的规律就是:相邻元素相差1,奇偶交替排列。
如果某个数A[i]等于要查找的数x,那么由于奇偶交替排列的关系,可以跳过下个数A[i+1],即i=i+2;
如果某个数A[i]不等于要查找的数x,那么由于相邻元素相差1,可以跳过x-A[i]的绝对值个数,即i=i+abs(x-A[i])
通过数组的规律来进行查找,可以减少一半以上的时间复杂度。
代码:
#include <iostream>
using namespace std;
void findX(int A[],int len,int x){
int tmp;
for(int i=0;i<len;){
if(A[i]==x){
cout<<i<<endl;
i=i+2;
continue;
}
tmp=x-A[i];
i=i+(tmp>=0?tmp:-tmp);
}
}
int main()
{
int A[]={1,2,1,2,3,4,3,4,5};
int len=sizeof(A)/sizeof(A[0]);
int x=4;
findX(A,len,x);
return 0;
}