[经典面试题][百度]数组A中任意两个相邻元素大小相差1，在其中查

题目

数组A中任意两个相邻元素大小相差1，现给定这样的数组A和目标整数t，找出t在数组A中的位置。如数组：[1,2,3,4,3,4,5,6,5]，找到4在数组中的位置。

思路

这道题目最差时间复杂度也是O（N），所以重点在于能不能找到一种尽可能减少比较次数的方法。

如数组：[1,2,3,4,3,4,5,6,5]，找到4在数组中的位置。4和1比较，差为3，那么即使最好情况（递增或者递减），4也就是在a［3］的位置，可以跳过a［1］a［2］。这样在特定数组（目标值和a［1］相差很大）的情况下或许可以节省时间。 所以得出规律：对于目标t,由当前位置a[i]比较开始，下一个可能位置为i = abs(a[i]-t)

代码

/*———————————————* 日期：2015-02-19* 作者：SJF0115* 题目: 相邻元素相差1，寻找目标整数t* 来源：* 博客：———————————————–*/;class Solution {public:int Find(int num[],int n,int target){if(n <= 0){return -1;}//iffor(int i = 0;i < n;){if(num[i] == target){return i;}//ifi += abs(num[i] – target);}//forreturn -1;}};int main() {Solution solution;int num[] = {1,2,3,2,3,4,3,2,3};int target = 4;cout<<solution.Find(num,9,target)<<endl;}

上面只是返回第一个目标位置，，如果题目要求返回所有的目标位置代码如下：

/*———————————————* 日期：2015-02-19* 作者：SJF0115* 题目: 相邻元素相差1，寻找目标整数t* 来源：* 博客：———————————————–*/;class Solution {public:vector<int> Find(int num[],int n,int target){vector<int> result;if(n <= 0){return result;}//iffor(int i = 0;i < n;){if(num[i] == target){result.push_back(i);i += 2;}//ifelse{i += abs(num[i] – target);}}//forreturn result;}};int main() {Solution solution;int num[] = {1,2,3,4,3,4,3,2,3,2,3,4};int target = 4;vector<int> result = solution.Find(num,12,target);for(int i = 0;i < result.size();++i){cout<<result[i]<<endl;}//for}

躲在某一时间想念一段时光的掌纹，