Leetcode lecture - 1252 Number of odd cells (difficulty: simple)

One 、 subject

To give you one  m*n  Matrix , At the very beginning , The value in each cell is 0.

There is another two-dimensional index array  indices,indices[i] = [ri, ci]  Point to a position in the matrix , among  ri  and  ci  Respectively represent the specified row and column （ from  0  Numbered starting ）.

Yes  indices[i]  Every position pointed , The following incremental operations should be performed at the same time ：

ri All cells on the row , Add 1 .
ci All cells on the column , Add 1 .

Here you are.  m、n  and  indices . Please finish executing all indices After the specified incremental operation , Back in the matrix   Odd cells   Number of .

Two 、 Example

2.1> Example 1：

【 Input 】m = 2, n = 3, indices = [[0,1],[1,1]]
【 Output 】6
【 explain 】 The initial matrix is [[0,0,0],[0,0,0]]. After the first incremental operation [[1,2,1],[0,1,0]]. The final matrix is [[1,3,1],[1,3,1]], There are 6 An odd number .

2.2> Example 2：

【 Input 】m = 2, n = 2, indices = [[1,1],[0,0]]
【 Output 】0
【 explain 】 The final matrix is [[2,2],[2,2]], There are no odd numbers in it .

Tips ：

1 <= m, n <= 50
1 <= indices.length <= 100
0 <= ri < m
0 <= ci < n

Advanced ：

You can design a time complexity of O(n + m + indices.length) And only O(n + m) Extra space algorithm to solve this problem ？

3、 ... and 、 Their thinking

3.1> solution 1： Mark the elements in the matrix with odd and even marks

The specific idea is , Every time an operation affects the value of an element of the matrix , For record , Put the coordinates of this element （x, y） As key, Take the specific value of this element as value, Save to map In structure , Because the final result is to check the number of odd numbers , therefore , When changing the element value , Change the total number of odd values together result This value .

Change logic ： Because the value of each element in the matrix value The initial value of 0, namely ： It's even . therefore result The initial value is equal to 0. So when the first execution value+1 When , because value Value is an odd value , therefore result Executive plus 1; If the second execution value+1 When , because value Value becomes an even value , therefore result At the same time, reduce 1 operation .

When all operations are completed ,result Value is the final number of odd cells . The specific logic is shown in the figure below ：

The advantage of this algorithm is , Thinking logic is more intuitive , It's easy to think of the solution at the first time . But its shortcomings are also obvious , Because the question only requires the number of odd units , You don't need to know the specific value of each element , So this solution is not optimal in space or time . solution 1 The concrete realization of Please refer to 4.1> Realization 1： Mark the elements in the matrix with odd and even marks .

3.2> solution 2： Count according to odd and even columns

Since we only get the number of odd cells , Then we try to find “ Odd cell ” Laws . A cell is made up of rows and columns . that ,indice The operation method of is to add all the element values of a row first 1, Then add all the element values of a column 1. Since it is operated like this , We can find a rule of odd cells —— That is, rows and columns cannot be odd or even at the same time , That is to say, the parity of ranks should be different , So this cell （ Or elements ） The value of is odd . The specific logic is shown in the figure below ：

that , Let's calculate the matrix as m=3,n=5,indices = [[0,1],[1,1]], After the operation , How many odd cells . The specific operation is shown below ：

The solution is based on the formula we derived , The solution is no longer needed 1 Medium map To store the coordinates and specific values of each cell or element . Technical cells can be calculated only by row and column parity . The execution speed is also much faster . solution 2 The concrete realization of Please refer to 4.2> Realization 2： Count according to odd and even columns .

Four 、 Code implementation

4.1> Realization 1： Mark the elements in the matrix with odd and even marks

public int result = 0;

public int oddCells_slow(int m, int n, int[][] indices) {
    Map<String, Integer> map = new HashMap();
    for (int[] indice : indices) {
        compare(n, indice[0], true, map);
        compare(m, indice[1], false, map);
    }
    return result;
}

public void compare(int num, int indice, boolean reverse, Map<String, Integer> map) {
    for (int j = 0; j < num; j++) {
        String key = reverse ? (j + "," + indice) : indice + "," + j;
        Integer value = map.get(key);
        if (value == null) {
            result++;
            map.put(key, 1);
        } else {
            result = (value % 2 == 0) ? ++result : --result;
            map.put(key, ++value);
        }
    }
}

4.2> Realization 2： Count according to odd and even columns

public static int oddCells(int m, int n, int[][] indices) {
    boolean[] row = new boolean[m], column = new boolean[n];
    int rowNum = 0, columnNum = 0;
    for (int[] indice : indices) {
        rowNum += (row[indice[0]] = !row[indice[0]]) ? 1 : -1; //  Calculation 【 Odd line 】 The number of 
        columnNum += (column[indice[1]] = !column[indice[1]]) ? 1 : -1; //  Calculation 【 Odd columns 】 The number of 
    }

    // 【 p. 】 Row number  * 【 accidentally 】 Number of columns  + 【 p. 】 Number of columns  * 【 accidentally 】 Row number 
    return rowNum * (n - columnNum) + columnNum * (m - rowNum); 
}

That's all for today's article , Last sentence ：

Writing is not easy to , An article completed by the author in hours or even days , I just want to get your praise for a few seconds & Share .

More technical work , Welcome everyone to follow the official account “ Java Muse ”(^o^)/~ 「 Dry cargo sharing , Weekly update 」

Title source ： Power button （LeetCode）