算法-面试题系列(一) 题目六 - 构造出特殊数组

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

返回构造出的arr

构建种子 如果数组只有一个元素[1] 达标

假设现在认为的构建一个种子数组三个元素 arr=[1,3,2] 对arr 做奇变换 *2-1 arr=[1,5,3] 也是满足条件的数组

假设arr=[a,b,c] a+c!=2b 那么[2a-1,2b-1,2c-1] 也满足

2a-1+2c-1 != 4b-2 还是a+c ！= 2b

同理 做偶变换 arr=[2a，2b，2c] 也满足 条件

想象我们要扩大数组，如果我们前面拿一个达标的奇数数组，后面拿一个达标的偶数数组， （*一个odd + 一个even 一定不会等于 2 * 一个num* ）的。所以，拼接起来的大数组一定是达标的。

[2a-1,2b-1,2c-1,2a，2b，2c] 也符合 对任意的i、j、 k三个位置，如果i<j<k， 都有arr[i] + arr[k] != 2*arr[j]

这样，我们就从3个数扩展成了6个数的数组。同样的道理，我们可以通过6个数，扩展成12个满足条件的数组。

[1] -> [1,2] -> [1,3,2,4] -> [1,5,3,7,2,6,4,8,] -->[1,9,5,13,3,11,7,15,2,10,6,14,4,12,8,16]

public class Code06_MakeNo {
    
    // 生成长度为size的达标数组
    // 达标：对于任意的 i<k<j，满足   [i] + [j]  != [k] * 2
    public static int[] makeNo(int size) {
        if (size == 1) {
            return new int[] { 1 };
        }
        // size
        // 一半长达标来
        // 7   :   4
        // 8   :   4
        // [4个奇数] [3个偶]
        int halfSize = (size + 1) >>1 ;
        int[] base = makeNo(halfSize);
        // base -> 等长奇数达标来
        // base -> 等长偶数达标来
        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;
    }
    

    // 检验函数
    public static boolean isValid(int[] arr) {
        int N = arr.length;
        for (int i = 0; i < N; i++) {
            for (int k = i + 1; k < N; k++) {
                for (int j = k + 1; j < N; j++) {
                    
                    
                    if (arr[i] + arr[j] == 2 * arr[k]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println("test begin");
        for (int N = 1; N < 1000; N++) {
            int[] arr = makeNo(N);
            if (!isValid(arr)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test end");
        
        System.out.println(isValid(makeNo(1042)));
        System.out.println(isValid(makeNo(2981)));
        

    }

}