面试标题搜集（3）

面试题目搜集（3）

1.有这样一个数组A，大小为n，相邻元素差的绝对值都是1。如：A={4,5,6,5,6,7,8,9,10,9}。现在，给定A和目标整数t，请找到t在A中的位置。除了依次遍历，还有更好的方法么？（来自新浪微博陈利人）

解法：数组第一个数为array[0], 要找的数为y，设t = abs(y - array[0])。由于每个相邻的数字之差的绝对值为1。故第t个位置之前的数肯定都比y小。因此直接定位到array[t]，重新计算t，t = abs(y – array[t])，再重复上述步骤即可。这种算法主要利用了当前位置的数与查找数的差来实现跨越式搜索。算法效率要比遍历数组的算法要高一些，并且易于实现。

#include <iostream>#include <cmath>#include <exception>using namespace std;typedef int Index;void Swap(int &a, int &b){int temp = a;a = b;b = temp;}//解法1// int FindNotReaptedNum(int arr[],int len)// {// if(!arr||len<0)// throw new runtime_error("Invalid Input");// // for(int i=0; i<len; ++i){// while(arr[i] != i){// if(arr[i] == arr[arr[i]])// return arr[i];// Swap(arr[i],arr[arr[i]]);// }// }// // return -1;// }//解法2int FindNotReaptedNum(int arr[],int len){if(!arr||len<0)throw new runtime_error("Invalid Input");for(int i=0; i<len; ++i){if(arr[i] > 0){if(arr[arr[i]]<0)return arr[i];arr[arr[i]] = -arr[arr[i]];}else{if(arr[-arr[i]]<0)return -arr[i];arr[-arr[i]] = -arr[-arr[i]];}}return -1;}void PrintArray(int arr[],int len){if(!arr||len<0)throw new runtime_error("Invalid Input");for(Index iter=0; iter<len; ++iter){cout<<arr[iter]<<" ";}cout<<endl;}int main(){const int ARR_MAX = 10;int arr[ARR_MAX]={2,5,3,5,6,7,8,9,10,1};    PrintArray(arr,ARR_MAX);cout<<"在数组重复的数为：";cout<<FindNotReaptedNum(arr,ARR_MAX)<<endl;system("pause");    return 0;}