作者dont (dont)
標題Re: [閒聊] 每日leetcode
時間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]]
```
--
※ 發信站: 批踢踢實業坊(ptt-website.tw), 來自: 185.213.82.172 (臺灣)
※ 文章網址: https://ptt-website.tw/Marginalman/M.1721358318.A.AC3
推 sustainer123: 大師 07/19 11:06