LeetCode 932. 漂亮数组 JAVA

￡神魔★判官ぃ 2022-12-13 01:24 48阅读 0赞

对于某些固定的 N，如果数组 A 是整数 1, 2, …, N 组成的排列，使得：  
对于每个 i < j，都不存在 k 满足 i < k < j 使得 A\[k\] \* 2 = A\[i\] + A\[j\]。  
那么数组 A 是漂亮数组。  
给定 N，返回任意漂亮数组 A（保证存在一个）

示例 1：
    
    输入：4
    输出：[2,1,4,3]
    示例 2：
    
    输入：5
    输出：[3,1,2,5,4]

题解：  
漂亮数组有以下的性质:

（1）A是一个漂亮数组，如果对A中所有元素添加一个常数，那么Ａ还是一个漂亮数组。

（2）A是一个漂亮数组，如果对A中所有元素乘以一个常数，那么A还是一个漂亮数组。

（3）A是一个漂亮数组，如果删除一些A中一些元素，那么A还是一个漂亮数组。

（4) A是一个奇数构成的漂亮数组，B是一个偶数构成的漂亮数组，那么A+B也是一个漂亮数组  
比如:\{1,5,3,7\}+\{2,6,4,8\}=\{1,5,3,7,2,6,4,8\}也是一个漂亮数组。

所以我们假设一个\{1-m\}的数组是漂亮数组，可以通过下面的方式构造漂亮数组\{1-2m\}:

对\{1-m\}中所有的数乘以2-1，构成一个奇数漂亮数组A。如\{1,3,2,4\},可以得到\{1,5,3,7\}  
对\{1-m\}中所有的数乘以2,构成一个偶数漂亮数组B,如\{1,3,2,4\}, 可以得到\{2,6,4,8\}  
A+B构成了\{1-2m\}的漂亮数组。\{1,5,3,7\}+\{2,6,4,8\}=\{1,5,3,7,2,6,4,8\}  
从中删除不要的数字即可。

class Solution {
        
        public int[] beautifulArray(int N) {
        
        int array[] = new int[2000];
        int array2[] = new int[N];
        int k =0;
        array[0] = 2;
        array[1] = 1;
        array[2] = 4;
        array[3] = 3;
        for(int i = 1;i<200;i*=2){
        
            for(int j = 0;j<i*4;j++){
        
                array[i*4+j] = array[j]*2;
                array[j] = array[j]*2-1;
            }
        }
        for(int i = 0;i<2000;i++){
        
            if(k<N&&array[i]!=0&&array[i]<=N){
        
               
                array2[k] = array[i];
                k++;
            }       
        }
        return array2;
        }
    }