This article is participating in Python Theme Month. See the link for details

describe

Given a rows x cols matrix mat, where mat[i][j] is either 0 or 1, return the number of special positions in mat.

A position (i,j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed).

Example 1:

Input: mat = [[0, 1], [0, 1], [0, 1]] Output: 1 Explanation: (1) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0.Copy the code

Example 2:

Input: mat = [[1,0,0], [0,1,0]] Output: 3 Explanation: (0,0), (1,1) and (2,2) are special positions.Copy the code

Example 3:

,0,0,1 Input: mat = [[0],,0,0,0 [1], [0,1,1,0], [0,0,0,0]] Output: 2Copy the code

Example 4:

,0,0,0,0 Input: mat = [[0],,0,0,0,0 [1], [0,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1]] Output: 3Copy the code

Note:

rows == mat.length
cols == mat[i].length
1 <= rows, cols <= 100
mat[i][j] is 0 or 1.
Copy the code

parsing

How many special numbers are there in mat? A special number must be 1 in a row and a column with zeros everywhere else. Directly use the built-in function to calculate the sum H and V in the horizontal and vertical directions, and then traverse the elements in MAT. As long as the element is 1 and the sum of the elements in the row and column is 1, then add one to the result, and the result can be obtained after the traverse. Of course, as is my habit, I don’t recommend this use of built-in functions.

answer

class Solution(object): def numSpecial(self, mat): """ :type mat: List[List[int]] :rtype: int """ import numpy as np mat = np.array(mat) v = np.sum(mat,0) h = np.sum(mat,1) result = 0 for i in range(len(mat)): if h[i]! =1: continue for j in range(len(mat[0])): if mat[i][j]==1 and v[j]==1 and h[i]==1: result += 1 break return resultCopy the code

The results

Runtime: Given in the linked list. Memory Usage: 13 MB, less than 5.43% of Python online submissions for Special Positions ina Binary Matrix.Copy the code

parsing

Directly traverse each row of matrix MAT, and calculate the number of 1 in each row, find the index of 1, and then calculate whether the number of 1 in the column where the index is located is also only one, if so, then the counter result is increased by one. The result obtained at the end of traversal is the final result. It turns out that this method is faster and requires less memory.

answer

class Solution(object):
    def numSpecial(self, mat):
        """
        :type mat: List[List[int]]
        :rtype: int
        """
        result = 0
        for i in range(len(mat)):
            if mat[i].count(1) == 1:
                i = mat[i].index(1)
                col = [row[i] for row in mat]
                if col.count(1) == 1:
                    result += 1
        return result
Copy the code

The results

Runtime: Given in the linked list. Memory Usage: 13 MB, less than 87.14% of Python online submissions for Special Positions ina Binary Matrix.Copy the code

Original link: leetcode.com/problems/sp…

Your support is my biggest motivation