前段时间在网上看到这么一个数字查找题，觉得挺有意思的，在此记录一下 。 大意是这样描述的：
有一个整型数组，它相邻两个元素只差的绝对值为 1 ，如： 7,8,9,10,11,10,9,8,7,6,5,4,3,2,1,0，-1,-2，-3，-4..... 现在要查找一个数 number ， 请找出number在数组中第一个出现的位置 。
其它的方法就不多说了， 下面讲一下一个比较 “另类”的解法。
数组第一个元素的值为array[0] ， 利用数组绝对值差为 1 的特性 ，如果number != array[0] , 则在array[0] ~~ array[ | number - array[0] | ] 之间的数都是比number 大 或者比number小的数 , 也就是说number最有可能出现的位置是 i = |number - array[0] | ， 如果 number != array[i] ,
则下一个最有可能出现的位置是 j = | number - array[i] | ...... 以此类推。 如果找到相等的数，则返回该数在数组中的位置 position ， 否则 返回 -1 。
下面是个简单的实现：
生成一个满足该规则的指定长度的数组
public static int[] genArrayData(int length) {
int[] data = new int[length];
Random r = new Random();
int key = length * 4 ;
data[0] = r.nextInt(key);
for (int i = 1; i < length; i++) {
data[i] = data[i - 1] + (r.nextInt(key) > data[i - 1] ? 1 : -1);
}
return data;
}
查找number在数组中第一次出现的位置：
public static int findNumInArray(int[] sour, int value) {
if (sour == null || sour.length == 0)
return -1;
int count = 0;
for (int i = 0; i < sour.length; i += Math.abs(value - sour[i])) {
System.out.println("compute time : " + ++count);
if (sour[i] == value)
return i;
}
return -1;
}
测试代码：
public static void main(String[] args) {
s_sour_data = genArrayData(10000000);
for (int i = 0; i < s_sour_data.length; i++) {
System.out.print(s_sour_data[i] + " ");
if(((i+1)%100) == 0)
System.out.println();
}
System.out.println();
System.out.println(findNumInArray(s_sour_data, 10989));
}
对于该问题就先写到这里了，若有不足，以后再做补充 ~_~！