链接：https://leetcode.cn/problems/cells-with-odd-values-in-a-matrix/solution/by-xun-ge-v-ekcm/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

暴力枚举法
1、初始化一个m*n的数组空间并初始化为0
2、按indices的元素对数组空间进行+1操作
3、最后遍历整个数组空间找到奇数个数并返回

空间优化
由于每次操作只会将一行和一列的数增加1，因此我们可以使用一个行数组rows 和列数组cols 分别记录每一行和每一列被增加的次数。对于indices 中的每一对 [r_i, c_i]我们将rows[r_i]和cols[c_i]的值分别增加 1。
在所有操作完成后，我们可以计算出位置 (x, y)位置的计数即为rows[x]+cols[y]。遍历矩阵，即可得到所有奇数的数目。

解释一下为什么rows[i]&1可以区分奇偶性，因为奇数的二进制数最后一位一定为1，而偶数二进制数最后一位一定为0，按位与上1，则只会保留当前元素二进制数的最后一位，即可区分奇偶

代码

暴力枚举法

int oddCells(int m, int n, int** indices, int indicesSize, int* indicesColSize){
    int ** ans = malloc(sizeof(int *) * m);
    //初始化空间
    for(int i = 0; i < m; i++)
    {
        ans[i] = malloc(sizeof(int) * n);
        memset(ans[i], 0, sizeof(int) * n);
    }
    //按行列加1
    for(int i = 0; i < indicesSize; i++)
    {
        int j = 0, k = 0;
        while(j < n)
        {
            ans[indices[i][0]][j++]++;
        }
        while(k < m)
        {
            ans[k++][indices[i][1]]++;
        }
    }
    //寻找奇数
    int sum = 0;
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(ans[i][j] % 2 != 0)
            {
                sum++;
            }
        }
        free(ans[i]);
    }
    free(ans);
    return sum;
}

空间优化

int oddCells(int m, int n, int** indices, int indicesSize, int* indicesColSize) {
    int res = 0;
    int *rows = (int *)malloc(sizeof(int) * m);
    int *cols = (int *)malloc(sizeof(int) * n);
    memset(rows, 0, sizeof(int) * m);
    memset(cols, 0, sizeof(int) * n);
    for (int i = 0; i < indicesSize; i++) {
        rows[indices[i][0]]++;
        cols[indices[i][1]]++;
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if ((rows[i] + cols[j]) & 1) {
                res++;
            }
        }
    }
    free(rows);
    free(cols);
    return res;
}

时间空间复杂度