Preface explains

Algorithm learning, daily brush problem record.

Subject to connect

A special position in a binary matrix

The subject content

Give you a matrix MAT of size Rows *cols, where mat[I][j] is 0 or 1, return the number of special positions in matrix MAT.

Special position definition: The position (I, j) is called a special position if mat[I][j] == 1 and all other elements in row I and column J are 0(the subscripts of both row and column start at 0).

Example 1:

Input:

Output: 1.

Explanation :(1,2) is a special position because mat[1][2] == 1 and is in a row and column where all other elements are 0

Example 2:

Input:

Output: 3

Explanation :(0,0), (1,1) and (2,2) are all special positions

Example 3:

Input:

Output: 2

Example 4:

Input:

Output: 3

Tip:

rows == mat.length

cols == mat[i].length

1 <= rows, cols <= 100

Mat [I][J] is 0 or 1

The analysis process

Idea: Two matrix traversal, the time complexity is O(2nm), ignore the constant term, that is, O(nm), the first matrix traversal, find out the sum of row elements at each position, the sum of column elements; The second matrix traversal finds the position where the value is 1, and determines whether the sum of the row elements and the column elements at this position are all 1, because the special position specifies that all the other elements of the row and column corresponding to this element are 0 and themselves are 1, so the sum of their row elements is 1, and the sum of the column elements is also 1.

The first step

Define the sum of the row elements at each position, represented by the array rows; Defines the sum of the column elements at each position, represented by the array COLs.

The second step

The first matrix walk, the sum of the row elements at this position, the sum of the column elements, by summation.

The third step

We iterate through the characters of string t, each time xOR the characters to res, and assign the result to res.

The fourth step

Let’s define the number of special positions in the matrix, count, and the second matrix traversal, if the value of this position is 1, and the sum of the row elements in this position is 1, and the sum of the column elements in this position is 1, then this position is the special position, the number of special positions in the matrix, count plus 1.

Step 5

Returns the number of special locations count in the matrix.

To solve the code

Class Solution {public int numSpecial(int[][] mat) {class Solution {public int numSpecial(int[][] mat) { The second matrix goes through the position where the value is 1, and determines whether the sum of the row elements and the column elements are all 1, because the special position specifies that all the other elements of the row and column corresponding to this element are 0 and themselves are 1, so the sum of their row elements is 1, Int [] rows = new int[mat.length]; int[] rows = new int[mat.length]; Int [] cols = new int[mat[0].length]; For (int I = 0; i < mat.length; ++i) { for (int j = 0; j < mat[i].length; ++j) {rows[I] += mat[I][j]; Cols [j] += mat[I][j]; }} // Define the number of special positions in the matrix int count = 0; For (int I = 0; i < mat.length; ++i) { for (int j = 0; j < mat[i].length; ++j) {if (mat[I][j] == 1 && rows[I] == 1 && cols[j] == 1) {// If (mat[I][j] == 1 && rows[I] == 1 && cols[j] == 1) {// if (mat[I][j] == 1 && rows[I] == 1 && cols[j] == 1) { The number of special positions in the matrix plus 1 ++count; } // Return the number of special positions in the matrix return count; }}Copy the code

Submit the results

The execution time was 2ms, beating 75.88% of users in time, 38.3MB in memory, and 90.27% in space.

The original link

A special location in a binary matrix