牛牛的交换排序题解

题解：我们可以对样例进行分析，发现原本为升序情况，返回YES即可，但是倘若是倒序，如果b数组中都是0或都是1情况下，是不能进行操作的，所以返回NO。那么我们可以再模拟几组用例，查看是否呈现出某种规律：
a,b -> a,b res
[3 2 1],[1 0 0] -> [1 2 3],[0 0 1] YES
[3 2 1],[1 1 0] -> [1 2 3],[0 1 1] YES
[3 2 1],[1 0 1] -> [2 3 1],[0 1 1] -> [1,3,2],[1,1,0] -> [1,2,3],[1,0,1] YES
我们可以发现，如果b数组不都为0或不都为1，那么一定可以通过交换得到升序数组。
根据以上推论，代码如下：
时间复杂度
空间复杂度

class Solution {
public:
    /**
     * 返回牛牛是否可以排序成功(从小到大)，如果可以，返回"YES"，反之，返回"NO"。
     * @param n int整型 代表a数组和b数组的元素数量
     * @param a int整型vector 代表a数组
     * @param b int整型vector 代表b数组
     * @return string字符串
     */
    string solve(int n, vector<int> &a, vector<int> &b)
    {
        // write code here
        int i, j, cnt = 0;
        for (i = 0; i < n; i++)
            if (b[i])
                cnt++;
        if (cnt == 0 || cnt == n)
        {
            for (i = 1; i < n; i++)
                if (a[i - 1] > a[i])
                {
                    return "NO";
                }
        }
        return "YES";
    }
};