Re: [闲聊] 每日leetcode

楼主: dont   2024-07-19 11:05:16
1380. Lucky Numbers in a Matrix
## 思路
解法1
照直觉写, 用两个阵列纪录min/max
解法2
看讨论只有一个lucky number
扫整个matrix纪录可能是lucky number的idx
idx一开始没默认-1死在测资
[[76618,42558,65788,20503,29400,54116]]
## Complexity
Time: O(MN)
解法1 Space: O(M+N)
解法2 Space: O(1)
## Code
解法1
```python
class Solution:
def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
len_r, len_c = len(matrix), len(matrix[0])
min_in_rows = [float('inf')] * len_r
max_in_cols = [float('-inf')] * len_c
for r in range(len_r):
for c in range(len_c):
min_in_rows[r] = min(min_in_rows[r], matrix[r][c])
max_in_cols[c] = max(max_in_cols[c], matrix[r][c])
ans = []
for r in range(len_r):
for c in range(len_c):
if matrix[r][c] == min_in_rows[r] == max_in_cols[c]:
ans.append(matrix[r][c])
return ans
```
解法2
```python
class Solution:
def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
len_r, len_c = len(matrix), len(matrix[0])
idx_r = idx_c = -1
for r in range(len_r):
# min in row
min_c = 0
for c in range(1, len_c):
if matrix[r][c] < matrix[r][min_c]:
min_c = c
# max in col
if idx_r == -1 or matrix[r][min_c] > matrix[idx_r][idx_c]:
idx_r, idx_c = r, min_c
for r in range(len_r):
if matrix[r][idx_c] > matrix[idx_r][idx_c]:
return []
return [matrix[idx_r][idx_c]]
```
作者: sustainer123 (caster)   2024-07-19 11:06:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com