题解 | #牛牛排队#

题目：
n个人排成一队，对于每个人来说。他左部分和右部分的人数差的绝对值是不变的，则对于a数组有多少种排队的方法

方法一：排序+迭代求幂

• 对于一个a数组，当调换第一个和最后一个，第二个和倒数第二个...的时候，被调换位置的人左右部分人数差的绝对值不变，即a数组不变，因为调换一次产生2种队列，可以调换n/2次，有种队列
• 如果数组合法就求,否则直接返回0。为了更方便地判断数组是否是合法数组，我们将数组按递增顺序排序，显然，当n为偶数时，,当n为奇数时，，因此在偶数数组中一旦或者则返回false，在奇数数组中一旦就返回false，或者i从2到n-1，或者时返回false

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int solve (int n, int[] a) {
        // write code here
        int mod=1000000007;
        Arrays.sort(a);
        //检查数组是否合法，不合法直接返回0
        if(!check(n,a))return 0;
        int res=1;
        //求2^(n/2)
        for(int i=0;i<n/2;i++)
            res=(res*2)%mod;
        return res;
    }
    boolean check(int n,int[]a){
        boolean isEven=(n%2==0)?true:false;
        for(int i=0;i<n;i+=2){
            //如果是偶数长度,需要符合(1,1,3,3,5,5,7,7...)的序列，一旦不符合返回false,否则全部检查完后返回true
            if(isEven&&(a[i]!=a[i+1]||a[i]!=i+1))return false;
            //如果是奇数长度，需要符合(0,2,2,4,4,6,6...)的序列，一旦不符合返回false,否则返回true
            if(!isEven) {
                if(a[0]!=0)return false;
                if(i!=0&&(a[i]!=a[i-1]||a[i]!=i))return false;
            }
        }
        return true;
    }
}

复杂度：
时间复杂度：,至少循环n/2次
空间复杂度：,没有使用额外的空间
方法二：排序+快速幂
求时，我们也可以采用快速幂的做法，降低时间复杂度
快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。
如果指数是奇数时，我们抽出了一个底数的一次方，假如计算，这个我们先单独移出来,剩下的,又能够在执行“缩指数”操作了，把指数缩小一半，底数执行平方操作 ,把指数缩小一半，底数执行平方操作
此时，指数又变成了一个奇数1，按照上面对指数为奇数的操作方法，再抽出一个底数的一次方，这里即为，这个单独移出来，但是此时指数却变成了0，也就意味着我们无法再进行“缩指数”操作了。

最后的结果是9*6561，指数为奇数5时，此时底数为9。当指数为奇数1时，此时的底数为6561。因此最后求出的幂结果实际上就是在变化过程中所有当指数为奇数时底数的乘积。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
     int mod=1000000007;
    public int solve (int n, int[] a) {
        // write code here
        Arrays.sort(a);
        //检查数组是否合法，不合法直接返回0
        if(!check(n,a))return 0;
        //求2^(n/2)
        return fastpow(2,n/2);
    }
    boolean check(int n,int[]a){
        boolean isEven=(n%2==0)?true:false;
        for(int i=0;i<n;i+=2){
            //如果是偶数长度,需要符合(1,1,3,3,5,5,7,7...)的序列，一旦不符合返回false,否则全部检查完后返回true
            if(isEven&&(a[i]!=a[i+1]||a[i]!=i+1))return false;
            //如果是奇数长度，需要符合(0,2,2,4,4,6,6...)的序列，一旦不符合返回false,否则返回true
            if(!isEven) {
                if(a[0]!=0)return false;
                if(i!=0&&(a[i]!=a[i-1]||a[i]!=i))return false;
            }
        }
        return true;
    }
    //快速幂求2^(n/2)
    int fastpow(long base,int power){
        long result=1;
        while(power>0){
            //指数是奇数时底数的乘积
            if((power&1)==1){
                result=result*base%mod;
            }
            power>>=1;//power/=2
            base=base*base%mod;//底数平方
        }
        return (int)result;
    }
}

复杂度：
时间复杂度： ,快速幂算法的时间复杂度为 ,排序函数的时间复杂度为
空间复杂度：,额外变量的复杂度为常数级