谷歌的一道面试题,请大家集思广益

看了上面许多牛人的想法，我也把自己的想法写一下
思考题目主要是找出差值
我的思路是从数组的最后面两个数判断
排除1,1,1,1

如果最后一个数（arr(n)）大于前一个数(arr(n-1))
那就把arr（n-1）左移，直到比arr（n）大的时候的前一位数就应该是他原来的值
用arr（n）-左移后的值就可以的到差值。然后替换数组。

如果最后一个数（arr（n））小于前一个数(arr(n-1))
那循环左移，直到大于前一个数
Boolean flag = true
int i = 1;
while(flag){
  arr(n)>>i++;
  if(arr(n)>arr(n-1)){
  flag = flase
  }
}
然后arr(n)-arr(n-1)得到差值就可以推算出前面的数值

这个是递增数组
递减数组的话就从第一位和第二位比较就可以了。
也不知道想法有没有漏洞，请高手指正

你当时说出递归两个字，这道题就算过了。

0、首项和公差不能都为偶数，否则失真。
1、前两项绝对值大的那个是原值
2、若第n项是原值，那么第n+2*i项必为原值。

package com.cccode.dclist;

public class dclist {

	/**
	 * @author CC
	 * @param args
	 */

	public static void main(String[] args) {
		/********************* 生成原数组 **************************************/
		int arr[] = new int[20];
		int min = -331;
		int d = 32;
		for (int i = 0; i < arr.length; i++) {
			arr[i] = min + d * i;
		}
		System.out.print("原数组： {");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + ", ");
		}
		System.out.println("}");
		System.out.println("min = " + min + " d = " + d);

		/************************ 将原数组转化为求解数组 ***********************/
		for (int i = 0; i < arr.length; i++) {
			while (arr[i] % 2 == 0) {
				arr[i] /= 2;
			}
		}
		System.out.print("求解数组： {");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + ", ");
		}
		System.out.println("}");

		/*********************** 求出公差和最小值 ******************************/
		int min1 = 0;
		int d1 = 0;
		if (Math.abs(arr[0]) >= Math.abs(arr[1])) {
			d1 = (arr[2] - arr[0]) / 2;
			min1 = arr[0];
		} else {
			d1 = (arr[3] - arr[1]) / 2;
			min1 = arr[1] - d1;	
		}
		System.out.println("min1 = " + min1 + " d1 = " + d1);
	}

}

另外，数组长度须 >= 4

原数组： {31, 62, 93, 124, 155, 186, 217, 248, 279, 310, 341, 372, 403, 434, 465, 496, 527, 558, 589, 620, }
min = 31 d = 31
求解数组： {31, 31, 93, 31, 155, 93, 217, 31, 279, 155, 341, 93, 403, 217, 465, 31, 527, 279, 589, 155, }
min1 = 31 d1 = 31


原数组： {32, 63, 94, 125, 156, 187, 218, 249, 280, 311, 342, 373, 404, 435, 466, 497, 528, 559, 590, 621, }
min = 32 d = 31
求解数组： {1, 63, 47, 125, 39, 187, 109, 249, 35, 311, 171, 373, 101, 435, 233, 497, 33, 559, 295, 621, }
min1 = 32 d1 = 31


原数组： {31, 63, 95, 127, 159, 191, 223, 255, 287, 319, 351, 383, 415, 447, 479, 511, 543, 575, 607, 639, }
min = 31 d = 32
求解数组： {31, 63, 95, 127, 159, 191, 223, 255, 287, 319, 351, 383, 415, 447, 479, 511, 543, 575, 607, 639, }
min1 = 31 d1 = 32


原数组： {32, 64, 96, 128, 160, 192, 224, 256, 288, 320, 352, 384, 416, 448, 480, 512, 544, 576, 608, 640, }
min = 32 d = 32
求解数组： {1, 1, 3, 1, 5, 3, 7, 1, 9, 5, 11, 3, 13, 7, 15, 1, 17, 9, 19, 5, }
min1 = 1 d1 = 1


原数组： {-331, -300, -269, -238, -207, -176, -145, -114, -83, -52, -21, 10, 41, 72, 103, 134, 165, 196, 227, 258, }
min = -331 d = 31
求解数组： {-331, -75, -269, -119, -207, -11, -145, -57, -83, -13, -21, 5, 41, 9, 103, 67, 165, 49, 227, 129, }
min1 = -331 d1 = 31

原数组： {-331, -299, -267, -235, -203, -171, -139, -107, -75, -43, -11, 21, 53, 85, 117, 149, 181, 213, 245, 277, }
min = -331 d = 32
求解数组： {-331, -299, -267, -235, -203, -171, -139, -107, -75, -43, -11, 21, 53, 85, 117, 149, 181, 213, 245, 277, }
min1 = -331 d1 = 32

thihy  的答案思路不错，我想这这个题目要分情况，体现一个人分析问题的能力。受教了

设a为数列第一个元素，d为公差。
1. 如果d为偶数，a为偶数，等差数列全是偶数，按照上面的计算，等到的结果可能有两种：一种是仍然是等差数列（如果d/2仍然为偶数的话），另一种奇数项仍成等差数列
2. 如果d为偶数，a为奇数，等差数列全是奇数，变换后的等差数列不变
3. 如果d为奇数，a为偶数，等差数列呈 偶奇偶奇...状，变换后偶数项仍成等差数列
4. 如果d为奇数，a为奇数，等着数列呈 奇偶奇偶...状，变换成奇数项仍成等差数列

由此可见，变换的的数列只有三种情况
（1）全是奇数项的等差数列（原始数列可能是1，2两种情况）
（2）奇数项仍成等差数列的数列（原始数列可能是1，4两种情况）
（3）偶数项仍成等差数列的数列（原始数列是3的情况）

所以，单凭变换后的数列不一定能还原原始数列，但是有办法重新得到一个等差数列。

首先 等差数列的 公式 Xn=a+Y*(n-1);  (a为基础值，n为数组序号，y为差量，x为数组值)
得到数组 {a,a+y,a+2y,a+3y,a+4y,...}

通过规则可以得出a,y的奇偶性直接影响结果。

对于结果数组至少要4个以上，3个一下部分规则不使用 需要调整
x1,x2,x3,x4
1.(x1=x2=x3=x4){ x1倍数 }
2.if y=(x3-x1)/2 作为差值 验证 x2×2^N=x1+y,x4×2^N=x3+y
3.if y=(x4-x2)/2 作为差值 验证 x1×2^N=x2-y,x3×2^N=x4-y


最终可以得到数组的最小组合

lisgking
说得不错。从后向前的比较。因为是等差序列。只能求处最小原始序列、结果不为一。

public class Test {
	
	public static int[] getHY(int[] result){
		int[] ret = null;
		if(result == null){
			return null;
		}
		if(result.length <=2){
			return result;
		}
		ret = result;
		for(int i=result.length-1; i>0; i--){
			for(int j=0; j<i; j++){
				if(ret[i] <= ret[j]){
					ret[i] = ret [i]<<1;
				}
			}
		}
		return ret;
	}

	public static void main(String[] args) {
		int [] t = new int[]{1,1,3,1};
		int [] r = Test.getHY(t);
		for(int i=0; i<r.length; i++){
			System.out.println(r[i]);
		}
	}

}

public class test{
	public static void main(String[] args){
		int[] a = {-331, -299, -267, -235, -203, -171, -139, -107, -75, -43, -11, 21, 53, 85, 117, 149, 181, 213, 245, 277};
		int d = (a[2] - a[0])/2;
		for(int i = 0;i < a.length - 1; i++){
			if((a[i+1] - a[i] != d)){
				int x = a[i + 1] * 2;
				int y = a[i];
				if(x - y != d){
					while((x - y != d)){
						x *= 2;
					}
				}
				a[i + 1] = x;
			}
		}
		for(int i = 0;i < a.length; i++){
			System.out.println(a[i]);
		}
	}
}

代码只是体现一下思路，多多指教~