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

假设 数列长度>=4,

1,3 和 2,4 分别组成2对,
其中至少有1对是原数列中的值未变的值,

因此,只要对 1,3 和 2,4 分别做1次运算,即可,
步骤:
* 假设 1,3 值未变,求出 数列差 (3-1)/2,然后去验证 2,4,
  如果符合,则说明ok,完成,
  如果不符合,则 2,4 组合 一定是没变的,进入下一步
* 用 (4-2)/2,求出 数列差,然后反推出 1,3 的值,以及整个数列的值,
*

当等差为2的倍数的偶数数列时，哥表示很蛋痛

反向推导的过程不能实现，除非有第三个数组来记录原始数组元素的操作

public class Test {
public static void main(String[] args){
int[] a = {1,1,3,1};
//int[] a = {3,3,9,3};
while(true){
while(true){
int n;
if((n =checkIncre(a)) != -1){
a[n]=a[n]*2;
} else {
break;
}
}
if(checkDengCha(a)){
break;
}
}
print(a);
}
private static int checkIncre(int[] a){
for(int i=0;i<a.length-1;i++){
if(a[i] >= a[i+1])
return i+1;
}
return -1;
}
private static boolean checkDengCha(int[] a){
int step = a[1]-a[0];
for(int i=2;i<a.length;i++){
if((a[i]-a[i-1])!=step)
return false;
}
return true;
}
private static void print(int[] a){
for(int i=0;i<a.length;i++){
System.out.print(a[i]+"\t");
}
}
}

输出：
1 2 3 4

测了一下 简单的是可以的
对于超大的数字未考虑，这个算法其实就是不断的尝试~~呵呵

int[] a = {1,1,3,1,5,3,7,1,9};
输出：
1 2 3 4 5 6 7 8 9

他让你写长点的意思是:不管偶数怎么变，总有一些是基数是不变的；比如你举得那个例子，a和c未变；再长点｛1，2，3，4，5，6，7，8｝，变换后｛1，1，3，1，5，3，7，1｝；那么｛a，c，e，g｝是未变的，他们的差值是就是他们列差*原来d；
至于找这些未变的数，不要我说吧，因为他们也是等差数列啊；
当然也有杯具的地方，如果原来的d=2。。。

恩。算法还是有问题
1： 2 4 6 8推不出来
2： 第一个数未考虑 已经除以2的情况

我是这么想的：用一个Map<index,radix> 记录数组变换的过程，index就是那些是偶数元素在数组中的索引，radix是除以2的次数，然后将变换后的数组根据这个Map来还原，编程应该好实现，后续分享代码。

import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

public class EvenAndOdd
{
	public EvenAndOdd(int... data)
	{
		super();
		this.data = data;

	}

	private int[] data;
	private int[] odds;
	private Map<Integer, Integer> map = new HashMap<Integer, Integer>();

	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		EvenAndOdd instance = new EvenAndOdd(1, 2, 3, 4, 5, 6, 7);
		int[] odds = instance.eliminateEven();
		System.out.println(Arrays.toString(odds));
		int[] result = instance.restore();
		System.out.println(Arrays.toString(result));

	}

	public int[] eliminateEven()
	{
		if (data == null || data.length == 0)
			return null;
		odds = new int[data.length];
		for (int i = 0; i < data.length; i++)
		{
			int origion = data[i];
			int evolved = origion;
			int radix = 0;
			while (evolved % 2 == 0)
			{
				evolved = evolved >> 1;
				map.put(i, ++radix);
			}
			odds[i] = evolved;
		}
		return odds;

	}

	public int[] restore()
	{
		if (odds == null || map.size() == 0)
			return data;
		Set set = map.entrySet();
		Iterator iter = set.iterator();
		while (iter.hasNext())
		{
			Entry<Integer, Integer> entry = (Entry<Integer, Integer>) iter.next();
			odds[entry.getKey()] = odds[entry.getKey()] << entry.getValue();
		}
		return odds;
	}
}

an = a1+nq
bn = to2(an)右移到非0位
1  
10
11
100


2=10=>1
4=100=>1
6=110=>3
8=1000=>1

1=1=>1
2=10=>1
3=11=>3
4=100=>1

等差数列的变换后差为2或2n次方不能直接返回

import java.util.Arrays;
import java.util.Random;

import org.apache.commons.lang.xwork.StringUtils;


public class to2 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Random r = new Random();
		for(int i = 0 ; i <10 ; i++){
			int a0 = Math.abs( r.nextInt(10));
			int q = Math.abs( r.nextInt(10)+1);
			long array[] = getArray(a0,q);
			System.out.println(Arrays.toString(array));
			long bin[] = getBinArray(array);
			System.out.println("\t"+Arrays.toString(bin));
			Arrays.equals(array, o);
		}
	}



	private static long[] getBinArray(long[] array) {
		long[] r = new long[array.length];
		for(int i =0 ; i <array.length;i++){
			String s = Long.toBinaryString(array[i]);
			s = StringUtils.substringBeforeLast(s,"1");//这个函数没找到用这个代替不过少一个1
			s+="1";
			r[i] = Long.parseLong(s,2);
		}
		return r;
	}

	private static long[] getArray(int a0, int q) {
		long[] l = new long[4];
		for(int i =0 ;i<4;i++){
			long an = 0l+a0+(1l*i*q);
			l[i]=an;
		}
		return l;
	}

	

}

要是不记录这个去偶的过程的话，即不依赖另外的数据结构来存储去偶的操作的话，只能从原始数组的奇数中找出规律来，来还原那些偶数的项。