[leetcode] Height Checker

5347 ワード
python algorithm テキストリンク
Height Checker

最初に思いついた方法


入力したリストをソートし、既存のリストと比較します.[1,1,4,2,3]->[1,1,2,3,4]3個違います!
class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        sortedHeights = sorted(heights)
        result = 0
        
        for index in range(len(heights)):
            if heights[index] != sortedHeights[index]:
                result += 1
                
        return result
こうしても通れるのですが、並べ替えなくても解ける方法が気になります.

他人を解く


を行ないます.hightsの数字の個数をfreqに記入し、hightsの順番と異なる場合はresult += 1を行います.
class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        result = 0
        curHeight = 0
        freq = [0]*101
        
        for height in heights:
            freq[height] += 1
        
        for i in range(len(heights)):
            while freq[curHeight] == 0: curHeight += 1
            
            if curHeight != heights[i]:
                result += 1
            
            freq[curHeight] -= 1
        
        return result
freqはheightの長さに関係なく一定の大きさを有するが,while文ではfreqの大きさのためwhile文はO(1)である.従って,for‐whileは高さの長さに比例し,全体としてO(N)であった.

参考資料


John Leonardo
Yii-ビュー-CGridViewリストの使い方の詳細.
U 3 D呼び出し7 zファイルの解凍