题目意思

• 给出每个编号的左右两边的差的绝对值，然后我们需要找出所有的满足题目条件的排列的情况数。

思路分析

• 我们发现，对于一个序列，只要位置是固定的，那么它的左右两边的差值也是固定的，与这个位置的是哪个数字其实是没有关系的。所以其实数组里面的数字的都是固定了的。我们只需要判断这个序列是否合法就行了。

  • 对于奇数的情况，我们发现第一个位置差值的绝对值应该是n-1,第二个位置是n-3,然后到了中间的位置的是否，左右两边的人数都是一样的，所以应该是0，过了中间的那部分，就和左边的对称了。所以奇数的情况应该是0出现一次，小于等于n的偶数出现两次，这样就是符合的。然后这个序列对称的那两个位置上面放的数字可以互相调换，所以如果序列是合法的，那么方案数就是$2^{n/2}2^\{n/2\}$2n/2。
  • 对于偶数的情况。我们发现第一个位置的差值的绝对值应该是n-1,第二个位置上面的就是n-3,然后一直类推，同理，偶数的话就是小于等于n的奇数出现的次数都是偶数次。序列合法的话总的方案数就是$2^{n/2}2^\{n/2\}$2n/2
  • 这里介绍一下快速幂的思想，快速幂就是我们假如要计算一个很大的幂次方$a^{b}a^b$ab，线性时间内求出来的时间复杂度是很大的，所以我们使用对数级别的时间复杂度。首先，如果这个b是一个奇数，那么可以拆分成(奇数+偶数)的情况。如果是偶数的情况，那么就可以将偶数拆分成两半，然后我们只需要计算一半即可，这样就将时间复杂度逐级下降了。我们发现，关键点就是偶数的情况，因为这样的话，我们就可以将计算规模下降了。

• 结合下图进行思考

思路一 哈希

• 由于需要记录每个数字出现的次数来判断序列是否合法，那么我们就可以利用$unordered\_mapunordered\backslash \_map$unordered_map进行哈希处理，然后最后通过循环进行判断即可。
• 代码如下
  • unordered_map哈希的时间复杂度是$O\left(1\right)O(1)$O(1),循环遍历序列的时间复杂度为$O\left(n\right)O(n)$O(n),总的时间复杂度为$O\left(n\right)O(n)$O(n)
  • 利用$unordered\_mapunordered\backslash \_map$unordered_map进行哈希，空间复杂度为$O\left(n\right)O(n)$O(n)

详细版

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型vector 
     * @return int整型
     */
    typedef long long ll;
    const int mod = 1e9+7;
    // 利用快速幂的写法来处理幂次方取模问题
    ll qp(ll a,ll b){
        if(b==0) return 1;
        // 如果指数是奇数，那么拆成奇数和偶数的情况
        if(b&1) return a*qp(a,b-1)%mod;
        else{
        	// 进行递归处理，只需要计算一半
            ll mul=qp(a,b/2);
            return mul*mul%mod;
        }
    }
    int solve(int n, vector<int>& a) {
        // write code here
        unordered_map<int,int> mp;
        for(auto x:a){
            mp[x]++;
        }
        // 分奇数和偶数进行讨论
        if(n%2==0){
            for(int i=1;i<=n;i+=2){
                if(mp[i]!=2){
                    return 0;
                }
            }
            
            ll ans=qp(2,n/2);
            return ans;
        }else{
            // 奇数的情况需要特判0出现的次数
            if(mp[0]!=1){
                return 0;
            }
            for(int i=2;i<=n;i+=2){
                if(mp[i]!=2){
                    return 0;
                }
            }
            
            ll ans=qp(2,n/2);
            return ans;
        }
    }
};

简化版

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型vector 
     * @return int整型
     */
    typedef long long ll;
    const int mod = 1e9+7;
    // 快速幂求幂次方取模运算
    ll qp(ll a,ll b){
        if(b==0) return 1;
        if(b&1) return a*qp(a,b-1)%mod;
        else{
            ll mul=qp(a,b/2);
            return mul*mul%mod;
        }
    }
    int solve(int n, vector<int>& a) {
        // write code here
        unordered_map<int,int> mp;
        // 先进行一次遍历，记录每个数字出现的次数
        for(auto x:a){
            mp[x]++;
        }
        // 如果是奇数的情况我们需要判断0的出现的次数
        if(n&1){
            if(mp[0]!=1){
                return 0;
            }
        }
        for(int i=n&1?2:1;i<=n;i+=2){
        // 如果存在其中的两个数字不是出现了两次，那么一定没有符合
           if(mp[i]!=2){
                return 0;
            }
        }
            
        ll ans=qp(2,n/2);
        return ans;
    }
};

解法二 排序

• 上一种写法我们使用的是哈希的方法进行处理，这次我们使用先排序来处理。我们先对序列从小到大进行排序。然后由于合法的序列只存在两个相等的数字，所以我们可以两两进行比较就行了。循环的步长设置为2。
• 代码如下
  • 进行排序的时间复杂度为$O\left(nlogn\right)O(nlogn)$O(nlogn),所以总的时间复杂度为$O\left(nlogn\right)O(nlogn)$O(nlogn)
  • 基本没有开其余数组进行处理，空间复杂度为$O\left(1\right)O(1)$O(1)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型vector 
     * @return int整型
     */
    typedef long long ll;
    const int mod = 1e9+7;
    // 快速幂求幂次方取模运算
    ll qp(ll a,ll b){
        if(b==0) return 1;
        if(b&1) return a*qp(a,b-1)%mod;
        else{
            ll mul=qp(a,b/2);
            return mul*mul%mod;
        }
    }
    int solve(int n, vector<int>& a) {
        // write code here
        sort(a.begin(),a.end());
        int l=0,r=n-1;
        // 分奇数和偶数的情况进行讨论处理
        if(n&1){
            // 奇数特判0的情况
            if(a[0]!=0){
                return 0;
            }
            // 判断两两相邻的是否相等，而且要等于当前下标+1
            for(int i=1;i<n;i+=2){
                if(a[i]!=a[i+1]||a[i]!=i+1){
                    return 0;
                }
            }
        }else{
            // 偶数同理
            for(int i=0;i<n;i+=2){
                if(a[i]!=a[i+1]||a[i]!=i+1){
                    return 0;
                }
            }
        }
        // 最后返回2的序列长度一半次幂
        ll ans=qp(2,n/2);
        return ans;
    }
};