1380. lucky numbers in matrices

difficulty ： Simple

Catalog

One 、 Problem description

Two 、 Ideas

1、 Their thinking

3、 ... and 、 Problem solving

1、 Code implementation

2、 Time complexity and Spatial complexity

---

One 、 Problem description

I'm going to use LeetCode The description above .

To give you one m * n Matrix , The number in the matrix Each are not identical . Please press arbitrarily Return all the lucky numbers in the matrix in order .

Lucky number refers to the elements in the matrix that meet the following two conditions at the same time ：

• The smallest of all elements in the same row
• The largest of all elements in the same column

Here is an example ：

Tips ：

• m == mat.length
• n == mat[i].length
• 1 <= n, m <= 50
• 1 <= matrix[i][j] <= 10^5
• All elements in the matrix are different

Two 、 Ideas

1、 Their thinking

        What I'm using here is progressive scanning , Scan one line at a time , Seeking to travel The smallest number , Returns the minimum number of the row and its subscript . Subscript according to the minimum number of rows , Find the largest number in the column , If meet ：

• The smallest of all elements in the same row
• The largest of all elements in the same column

that , Save the element in a container , Until all rows are scanned , Just return the answer directly .

3、 ... and 、 Problem solving

1、 Code implementation

class Solution {
public:
    pair<int,int> minLine(vector<int>& nums,int length){
        int min = 0x1f1f1f1f,index = 0;
        for(int i = 0; i < length; i++){
            if(nums[i] < min){
                min = nums[i];
                index = i;
            }
        }
        return {min,index};
    }

    int maxRow(vector<vector<int>>& matrix,int rowLength,int rowNum){
        int maxNum = 0;
        for(int i = 0; i < rowLength; i++){
            maxNum = max(maxNum,matrix[i][rowNum]);
        }
        return maxNum;
    }

    vector<int> luckyNumbers (vector<vector<int>>& matrix) {
        // Save row element size 、 And column element size 
        int lineLength = matrix[0].size(), rowLength = matrix.size();
        vector<int> ans; 
        for(auto& it : matrix){
            // Scan a line , Get the minimum number of the row and its subscript 
            auto lineMinIndex = minLine(it,lineLength);
            // Subscript according to the minimum number of rows , Get the column number , Scan the column   Find the largest element of the column 
            int rowMax = maxRow(matrix, rowLength, lineMinIndex.second);
            // contrast   The minimum number of this line   Whether it is   The maximum number in the column 
            if(lineMinIndex.first == rowMax){
                ans.push_back(rowMax);
            }
        }
        return ans;
    }
};

 

2、 Time complexity and Spatial complexity

Time complexity ：,m And n Respectively Number of row and column numbers

Spatial complexity ：