牛牛满意的数组(二）题解

这题我们可以思考是否存在一个贪心策略:我们先试着根据题目的意思，统计a[i]%2==1的数量，再统计i%2==1的数量，若两者相等，那么这个数组才有可能使得牛牛满意，反之，返回-1。如果上述条件满足，那么我们发现，我们其实只需要继续统计 i%2 != a[i]%2的数量，最后将这个数量/2就是题目的答案（因为我们只需要交换那些不满足要求的，那么一定是最少交换次数了）。
时间复杂度
空间复杂度
代码如下：

class Solution {
public:
    /**
     * 如果能通过交换数组中的某些元素使得该数组让牛牛十分满意，请返回牛牛需要最少交换的次数，否则，请返回-1。
     * @param n int整型 代表数组中元素的数量
     * @param a int整型vector 代表数组中元素的大小
     * @return int整型
     */
    int solve(int n, vector<int> &a)
    {
        // write code here
        int i, ans = 0, ans0 = 0, ans1 = 0, ans00 = 0, ans11 = 0;
        for (i = 0; i < n; i++)
            a[i] %= 2;
        for (i = 0; i < n; i++)
            if (a[i])
                ans1++;
            else
                ans0++;
        for (i = 0; i < n; i++)
            if (i % 2)
                ans11++;
            else
                ans00++;
        if (ans1 != ans11)
            return -1;
        for (i = 0; i < n; i++)
            if (i % 2 != a[i])
                ans++;
        return ans / 2;
    }
};