题解 | #牛牛排队#

题意整理

n个人在排队，它们的位置可能被打乱了，有一个数组记录了一些信息。
数组中对应的那个人，记录着站在他左部分和站在他右部分的人的人数差的绝对值。
根据上面的信息，求他们可能的站法有多少种。

方法一（排序）

1.解题思路

如果有两个人，a数组只能是[1,1]，如果有三个人a数组只能是[2，0，2]，如果有4个人，a数组一定是[1,3,3,1]或者[1,3,3,1]打乱顺序后的样子。依此类推，n为奇数时，a一定是形如（0，2，2，4，4，6，6，……）的数组，n为偶数时，a一定是形如（1，1，3，3，5，5，……）的数组。数列a中报0的那个人一定在队伍的正中间，对于其他人，每一个不同的人数差的绝对值，都可以将他们对调一次位置，所以总共有 $图片说明$ 种可能的站法。

首先对数组a排序
如果数组a长度是偶数，要验证其是否是形如（1，1，3，3，5，5，……）的数组；如果数组a长度是奇数，要验证其是否是形如（0，2，2，4，4，6，6，……）的数组。
最后计算可能的站法数

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    //取余常数
    int mod=1000000007;
    public int solve (int n, int[] a) {
        //排序
        Arrays.sort(a);
        //判断a是否是合理的数组
        if(!check(a)) return 0;

        //计算可能的站法数
        int res=1;
        for(int i=0;i<n/2;++i){
            res = (res*2)%mod;
        }
        return res;
    }

    private boolean check(int[] a){
        int n=a.length;
        boolean isEven=(n%2==0);
        for(int i=0;i<n;i+=2){
            //如果是偶数，一定是形如（1，1，3，3，5，5，……）的序列
            if(isEven&&(a[i]!=a[i+1]||a[i]!=i+1)){
                return false;
            }
            //如果是奇数，一定是形如（0，2，2，4，4，6，6，……）的序列
            if(!isEven){
                if(a[0]!=0){
                    return false;
                }
                if(i!=0&&(a[i]!=a[i-1]||a[i]!=i)){
                    return false;
                }
            }
        }
        return true;
    }

}

3.复杂度分析

时间复杂度：排序的时间复杂度是 $O(nlog_2n)$ ，其他的遍历均是线性的，所以最终的时间复杂度是 $O(nlog_2n)$ 。
空间复杂度：需要额外常数级别的内存空间，所以空间复杂度是 $O(1)$ 。

方法二（排序+快幂法）

1.解题思路

此方法与方法一的思路大致相同，不过计算 $图片说明$ 时，使用了快幂法。
很多情况下乘方运算会超出数据范围，造成溢出，可以通过快幂法，在每次运算中通过取余的方式，防溢出，并且，如果有n个数相乘，快幂法的时间复杂度为 $O(log_2n)$ 。

动图展示（快幂法求指数）：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    //取余常数
    int mod=1000000007;
    public int solve (int n, int[] a) {
        //排序
        Arrays.sort(a);
        //判断a是否是合理的数组
        if(!check(a)) return 0;

        return fastpow(2,n/2);
    }

    private boolean check(int[] a){
        int n=a.length;
        boolean isEven=(n%2==0);
        for(int i=0;i<n;i+=2){
            //如果是偶数，一定是形如（1，1，3，3，5，5，……）的序列
            if(isEven&&(a[i]!=a[i+1]||a[i]!=i+1)){
                return false;
            }
            //如果是奇数，一定是形如（0，2，2，4，4，6，6，……）的序列
            if(!isEven){
                if(a[0]!=0){
                    return false;
                }
                if(i!=0&&(a[i]!=a[i-1]||a[i]!=i)){
                    return false;
                }
            }
        }
        return true;
    }

    //快幂法求指数运算
    private int fastpow(long base,int k){
        long res=1;
        while(k>0){
            if((k&1)==1){
                res=res*base%mod;
            }
            base=base*base%mod;
            k>>=1;
        }
        return (int)res;
    }
}

3.复杂度分析

时间复杂度：排序的时间复杂度是 $O(nlog_2n)$ ，快幂法求站法数的时间复杂度为 $O(log_2n)$ ，其他的遍历均是线性的，所以最终的时间复杂度是 $O(nlog_2n)$ 。
空间复杂度：需要额外常数级别的内存空间，所以空间复杂度是 $O(1)$ 。