本文主要是介绍查找——相邻元素差的绝对值都是1的数组当中的某个数，百度笔试题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目是这样的：
有这样一个数组A,大小为n，相邻元素差的绝对值都是1，如A={4,5,6,5,6,7,8,9,10,9}。现在给定数组A和目标整数t，请找到t在数组中的位置。
嗯，看到这个题目，想了一会儿，然后又想到《剑指offer》当中学到的分析问题的方法，那就是不管遇到什么题，举一两个例子，慢慢就可以看出规律了。于是乎就试验了一把这道题，不出所料，试了两步就想出了方法。
思路是这样的：假如我们要查找9，即t=9，然后我想的是，从数组第一个数开始，A[0]=4，那么t-A[0]=5，那么第二步再计算t-A[5]=2，此时5+2=7，A[7]就是目标数9了！因此这个方法就是从A[0]开始，然后逐步根据target与A[i]的差，来更新i，i=i+abs(target-A[i])，直到target在A[i]中找到。那么找不到的情况呢，那就是i会超过数组的长度，此时也是循环退出的时候。补充，此时i有可能大于length，也有可能小于0，比如当target取1的时候， i=i+1-4，此时i=-3，呵呵，对吧，i就跑到数组“左边”去了，也超出了数组范围，这个当时没有考虑清楚，这里加上。
分析：时间复杂度应该是常数级别的。
分享下代码：
// FindABSofSub_isOne_Array.cpp : 定义控制台应用程序的入口点。
/*@mishidemudong@2015-5-28\23:20*/
//#include "stdafx.h"
#include"math.h"
bool Find;
int FindABSofOne(int *a, int length, int target)
{if (a == NULL&&length < 0)Find = false;int i = 0;while (i <=length-1&&i >=0){if (a[i] == target){Find = true;return i;}else{i =i+ abs(target - a[i]);}}if (i > length|| i < 0)Find=false;
}int _tmain(int argc, _TCHAR* argv[])
{int A[11] = { 4, 5, 6, 5, 6, 7, 8, 9, 10, 9 ,8};int B[12] = { 6, 5, 4, 3, 2, 1, 2, 3, 2, 3, 4, 5 };int target = 0;int coordinate;printf("The Array is:\n");for (auto c : A)printf("%d, ", c);printf("\nWhich number do you want to search ?Condition thar the number is in the Array.\n");scanf_s("%d", &target);coordinate = FindABSofOne(A, 11, target);switch (Find){case false:printf("Sorry,the number you input is not in this Array"); break;case true:printf("Congratulations,the number you input is the %dth number of this Array",coordinate+1); break;}return 0;
}
这篇关于查找——相邻元素差的绝对值都是1的数组当中的某个数，百度笔试题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
