[Week 6-1] 🔥特集講座初日

第6週火曜日

個人学習

アルゴリズムの問題は久しぶりですね~

[LeetCode 1380. Lucky Numbers in a Matrix]

重複しない要素のm x n行列が与えられると、行列に存在するすべてのLucky numberが戻される
Lucky number:行の最小値、列の最大値.

に近づく
各行の最小値を検索し、最小値を属する列の最大値と比較します.
時間複雑度:O(m*n)=O(n^2)

コード#コード#

class Solution:
    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
        # lucky number : 자신이 속한 행에서는 최소, 열에서는 최대가 되는 수
        M = len(matrix[0])
        N = len(matrix)
        luckies = []
        
        for row in matrix:
            minNum = min(row)
            minIdx = row.index(minNum)
            
            col = [matrix[i][minIdx] for i in range(N)]
            if max(col) == minNum:
                luckies.append(minNum)
                
        return luckies
                

より速い方法はありませんか?
しょうげき
とてもPythonらしいコードを見つけました.ファスナーや解包の使い方は頭の中では知っていましたが、問題に応用されるとは思わなかった・・・行の最小値と列の最大値を別々に探して交差を求めるとは思わなかった.忘れずに使ってくださいね.
時間複雑度:O(N)?zipの時間的複雑さはよくわかりません.
Python 3からzipはiteratorオブジェクトとして動作するため,zipの時間的複雑度はO(N)である.Python 2ではzipはlistを返すため,時間的複雑度はO(N*M)である.

class Solution:
    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
        # lucky number : 자신이 속한 행에서는 최소, 열에서는 최대가 되는 수
        
        matrix_T = list(zip(*matrix))
        rowMin = []
        colMax = []
        
        for row in matrix: # 각 행에서의 최소값
            rowMin.append(min(row))
            
        for col in matrix_T: # 각 열에서의 최대값
            colMax.append(max(col))
                          
                          
        return set(rowMin) & set(colMax)