Re: [閒聊] 每日leetcode已回收
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.cc), 來自: 185.213.82.172 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721358318.A.AC3.html
推
07/19 11:06,
1年前
, 1F
07/19 11:06, 1F
討論串 (同標題文章)
完整討論串 (本文為第 526 之 1550 篇)：