leetcode

414. Third Maximum Number

どーも!

たかぽんです!

今回は以下の問題です!

問題は至って簡単で、数字が入った配列が渡されるため、その中から3番目に大きな値を返せ...というものです。

[1,2,3]

であれば、3番目に大きい値は1となります。

ただし...!

もし3番目に大きい物が無い場合は最も大きな値を返す必要があります。

[1,2]

なら、2となります。

さらに、重複がある場合は同一の値として判定します。

[1,2,2,3]

であれば、[1,2,3]と同じと考えて良いため、3番目に大きな値は1となります。

では...!

アルゴリズムを簡単に考えます。

アルゴリズム

アルゴリズムの検討をしていきます。

とはいっても、pythonの便利関数をガッツリ使っていく形で...

まず配列の中の重複をsetメソッドを使って消してあげます。

そして、その中をソートすると、左側が若い番号、右側が大きな値になります。

末尾から三つ手前の要素を取得すればいいのですが、わかりやすいようにreverseをかけて、先頭が最も大きな値、末尾が小さな値にしてから3番目の要素を取り出します。

その際、もし重複をのぞいた配列の要素数が3よりも小さい場合は0番目(最も大きな値)を返してあげます。

以上がざっくりとしたアルゴリズムです。

言葉だけだと難しいと思うの、最後に提出したコードを置いておきます。

参考にしてみてください。

提出したコード

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        ListedNums = list(set(nums))
        ListedNums.sort()
        ListedNums.reverse()
        if len(ListedNums) < 3:
            return ListedNums[0]
        return ListedNums[2]

## 結果
Runtime: 48 ms, faster than 89.12% of Python3 online submissions for Third Maximum Number.
Memory Usage: 15.9 MB, less than 26.00% of Python3 online submissions for Third Maximum Number.
おすすめの記事