Given a m * n
matrix of distinct numbers, return all lucky numbers in the matrix in any order.
A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.
Example 1:
Input: matrix = [[3,7,8],[9,11,13],[15,16,17]] Output: [15] Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column
Example 2:
Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]] Output: [12] Explanation: 12 is the only lucky number since it is the minimum in its row and the maximum in its column.
Example 3:
Input: matrix = [[7,8],[1,2]] Output: [7]
Constraints:
m == mat.length
n == mat[i].length
1 <= n, m <= 50
1 <= matrix[i][j] <= 10^5
.- All elements in the matrix are distinct.
Solution: Pre-processing
Two pass. First pass, record the min val of each row, and max val of each column.
Second pass, identify lucky numbers.
Time complexity: O(m * n)
Space complexity: O(m + n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua class Solution { public: vector<int> luckyNumbers (vector<vector<int>>& matrix) { const int m = matrix.size(); const int n = matrix[0].size(); vector<int> rows(m, INT_MAX); vector<int> cols(n, INT_MIN); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { rows[i] = min(rows[i], matrix[i][j]); cols[j] = max(cols[j], matrix[i][j]); } vector<int> ans; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (matrix[i][j] == rows[i] && matrix[i][j] == cols[j]) ans.push_back(matrix[i][j]); return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment