题解 | #牛牛排队#

思路：

题目的主要信息：

数组a表示n个人，记忆的他们原来的位置左边人数减去右边人数的绝对值
求原来有多少种排法

我们可以发现一个人的时候， $a=[0]$ ，两个人的时候， $a=[1,1]$ ，三个人的时候， $a=[2,0,2]$ ，四个人的时候， $a=[3,1,1,3]$ 或者其打乱了顺序，我们可以根据数学归纳法判断，若是 $n$ 为奇数，则数组a排序后应为 $[0,2,2,4,4,6,6...]$ ，若是 $n$ 为偶数，则数组a排序后应为 $[1,1,3,3,5,5...]$ ，其中数字0一定在中央，其他数字可以分别对换一次位置，因此总方案数为 $2^{n/2}$

方法一：排序+快速幂
具体做法：
首先对数组进行排序，然后根据奇偶人数检查数组是否是上述的形式，如若不是则无法构成正确的队列，如果是则根据公式，利用快速幂算出答案。
快速幂的解析如下：如果我们要计算 $5^{10}$ ，常规的算法是 $5*5=25$ ，然后再 $25*5=125$ ，如此往下，一共是 $9$ 次运算，即 $n-1$ 次。但是我们可以考虑这样： $5*5=25$ (二次）、 $25*25=625$ （四次）、 $625*625=...$ （八次），这是一个二分的思维，运算次数缩减到了 $log_2n$ 次，公式如下：
图片说明

class Solution {
public:
    long long Pow(long long x, long long y){ //快速幂
        long long res = 1;
        while(y){
            if(y & 1) //可以再往上乘一个
                res = res * x % 1000000007;
            x = x * x % 1000000007; //叠加
            y = y >> 1; //减少乘次数
        }
        return res;
    }
    int solve(int n, vector<int>& a) {
        if(n == 1)
            return a[0] == 0;
        sort(a.begin(), a.end()); //排序
        int num = 0, index = 0; //表示开始数字及下标
        if(n % 2 == 1){ //奇数
            if(a[0] != 0) //第一个数必须为0
                return 0;
            num = 2;
            index = 1;
        }else{ //偶数
            num = 1;
            index = 0;
        }
        while(index < n){ //检查是否是合理的数组
            if(a[index] != num || a[index + 1] != num)
                return 0;
            index += 2;
            num += 2;
        }
        return (int)Pow((long long)2, (long long)n / 2); //快速幂公式求结果
    }
};

复杂度分析：

时间复杂度： $O(nlog_2n)$ ，sort函数排序耗费 $O(nlog_2n)$ ，检查数组是否合法为 $O(n)$ ,公式计算为 $O(log_2n)$
空间复杂度： $O(1)$ ，常数级空间，无额外变量

方法二：数字统计法
具体做法：
我们找到前面的规律，除了奇数的数字0只出现一次外，其他的小于n的偶数会在n为奇数时都出现两次，其他的小于n的奇数会在n为偶数时都出现两次，我们可以利用这个规律，借助一个辅助数组统计所有数字出现的次数，根据奇偶检验该数字是否出现2次或者0次即可。最后的结果也是 $2^{n/2}$ ，我们只需要在偶数次时乘2即可。
图片说明

class Solution {
public:
    int solve(int n, vector<int>& a) {
        int mod = 1e9 + 7;
        int res = 1;
        vector<int> count(n, 0); //统计每个数字出现次数
        for(int i = 0; i < n; i++)
            count[a[i]]++;
        if(n % 2){ //奇数个人
            for(int i = 0; i < n; i++){
                if(i == 0){ //奇数的第一个是0
                    if(count[0] != 1)
                        return 0;
                }
                else{
                    if(i % 2 && count[i] != 0) //一定没有出现过
                        return 0;
                    if(i % 2 == 0 && count[i] != 2) //一定出现2次
                        return 0;
                    if(i % 2 == 0)
                        res = res * 2 % mod; //2^(n/2)，偶数次才乘2
                }
            }
        }else{ //偶数个人
            for(int i = 0; i < n; i++){
               if(i % 2 == 0 && count[i] != 0)
                    return 0;
               if(i % 2 && count[i] != 2)
                    return 0;
               if(i % 2 == 0)
                    res = res * 2 % mod;//2^(n/2)，偶数次才乘2
            }
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，不管是统计数字还是检验是否合法都是 $O(n)$ ，计算在检验的循环中
空间复杂度： $O(n)$ ，辅助数组count的长度