LeetCodeで学ぶ計算量の改善

計算量の改善

って意外と取り組む事がないなぁと最近思い始めて、一回解いた問題の回答をより良くできる方法を考えたりしている今日この頃です。

• 昔に比べてメモリの性能が改善しているためよっぽど致命的なアルゴリズムを設計しない限りはなんとかなる
• ソートなどのアルゴリズムはライブラリのものを呼び出せばなんとかなる
• etc…

色々な理由はあると思いますが、だからと言ってサボっていい理由にはならないと思うのでいい例を探していたらこんな問題を見つけました。

Majority Element

整数を格納したリストが与えられるのでそのリストの中で最も多い値を返してください、という問題です。

例えば、

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

といったような形式です。

今回はSolutionにもある通り、それぞれの問題に対する取り組み方を書きます。

例えばBruteforce。これはとにかく全パターンをしらみつぶしに実行して答えを導く、というものです。

class Solution:
    def majorityElement(self, nums):
        majority_count = len(nums)//2
        for num in nums:
            count = sum(1 for elem in nums if elem == num)
            if count > majority_count:
                return num

解けるものの、for文で2回走査しているため、計算量がO(N^2)とお世辞にもいいとは言えません。

では次にハッシュマップに格納して解く例です。

class Solution:
    def majorityElement(self, nums):
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)

こちらの場合、一度の走査で格納できるので、計算量はO(N)まで抑えられます。

最後にソートによって回答している例です。

class Solution:
    def majorityElement(self, nums):
        nums.sort()
        return nums[len(nums)//2]

これは計算量がO(NlogN)となっています。
ハッシュマップほどまで速くはないですが、これくらいの速度であれば十分でしょう。

まずはBruteforceでもいいのでひとまず解ける形に持っていく、その後計算量を少なくするにはどうしたらいいのか、というのを試行錯誤していくのが一つの楽しみ方かと思います。

今回はここまで。お疲れ様でした。