※ 引述《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] -- ※ 發信站: 批踢踢實業坊(ptt-website.tw), 來自: 123.194.160.111 (臺灣) ※ 文章網址: https://ptt-website.tw/Marginalman/M.1721354768.A.997

推 JerryChungYC: 大師 07/19 10:17

推 JIWP: 大師 07/19 10:25