※ 引述《JerryChungYC (JerryChung)》之銘言：
: https://leetcode.com/problems/lucky-numbers-in-a-matrix
: 1380. Lucky Numbers in a Matrix
: ※ 引述《DJYOMIYAHINA (通通打死)》之銘言：
: : 其實直覺來看
: : 就取個row的minimum與各col的maximum
: : 如果這兩個有交集就是答案了
: : 肥肥智商大概只到這裡
: : 後來看別人討論
: : 發現這個lucky number最多只有一個
: : 若存在兩個lucky number的話 假設是(i0,j0)跟(i1,j1)位置
: : 可以導出
: : M(i0,j0) > M(i1,j0) > M(i1,j1) > M(i0,j1) > M(i0,j0) -> 矛盾
: : 所以不可能有兩個lucky number
: : 然後這個lucky number
: : 也必然是 row minimums裡面的maximum 以及 col maximums裡面的minimum
: : 若不是row minimums裡面的maximum的話 假設是row minimums裡面第二大的
: : 代表那個column裡的值 都是比這個第二大的值小
: : 那就代表其他row有更小的值 然後就怎樣怎樣的我打不完了我要去上班了==
: Example 1:
: Input: matrix = [[ 3, 7, 8],
: [ 9,11,13],
: [15,16,17]]
: Output: [15]
: Example 2:
: Input: matrix = [[ 1,10, 4, 2],
: [ 9, 3, 8, 7],
: [15,16,17,12]]
: Output: [12]
: Example 3:
: Input: matrix = [[7,8],
: [1,2]]
: Output: [7]
: class Solution:
: def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
: # result = []
: for row in matrix:
: row_min = min(row)
: min_index = row.index(row_min)
: if row_min == max(_[min_index] for _ in matrix):
: # result.append(row_min)
: return [row_min]
: # return result
: return []
: 照直覺寫的 先找最小值 再根據index找最大值 符合就回傳
: 註解的是原本寫的 看這篇說只會有唯一解就改了一下
: 不過原本的成績更好 不太重要就是了 隨興的leetcode系統
: 好久沒打leetcode 剛好有個easy只好來騙騙p幣了
思路:
差不多 找到row的最小值 跟col的最大值
然後就有解了 不過不知道能不能再壓低時間複雜度
Python Code:
class Solution:
def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
min_row = []
max_col = []
for row in matrix:
min_row.append(min(row))
for i in range(len(matrix[0])):
cur = 0
for j in range(len(matrix)):
cur = max(cur,matrix[j][i])
max_col.append(cur)
for m in min_row:
if m in max_col:
return [m]