每天一道算法题7

【分治法 a + c != 2*b】
给定一个正整数M，请构造出一个长度为M的数组arr，要求对任意的i，j，k三个位置，如果i < j < k, 都有arr[i] + arr[k] != 2 *arr[j]

解答：这题有点跳，如果假设找到了三个数，a,b,c 满足a+c != 2 * b, 则（2a-1) + (2 * c - 1) != 2 * (2b -1), 同样，2a + 2b != 2c
所以就可以从3个数，构造成6个数，满足条件，左边是这三个数的奇数，右边是这三个数的偶数。
因为如果i,j,k都在左侧，满足条件，如果都在右侧，也是满足条件，如果i,j 在左侧，k 在右侧，则奇 + 偶 ！= 2 * 偶， 所以这样的组合一定满足条件。那6个数找到了，就一定能找到12个数，自然而然就都找到了。所以M一直除2，找到最小的数量满足条件，即1个数[1]

public class MakeNumber {
    public static int[] makeNumber(int size) {
        if (size == 1) {
            return new int[]{1};
        }
        int halfSize = (size + 1) / 2;
        int[] base = makeNumber(halfSize);
        int[] ans = new int[size];
        int index = 0;
        for (; index < halfSize;index++) {
            ans[index] = base[index] * 2 + 1;
        }

        for (int i = 0; index < size; index++, i++) {
            ans[index] = base[i] * 2;
        }
        return ans;
    }
}