ゼロから始めるLeetCode Day17「169. Majority Element」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day16 「344. Reverse String」
次回
ゼロから始めるLeetCode Day18 「53. Maximum Subarray」

問題

169. Majority Element

難易度はeasy。Top 100 Liked Questionsからの抜粋ですね。

与えられたnのサイズ配列の中で過半数を占める要素を見つけなさいというものです。
なお配列は空ではなく、過半数の要素が常に存在するものとする。

Example 1:
Input: [3,2,3]
Output: 3

Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2

両方とも過半数を占める物を返しています。

解法

組み込み関数countを使うのも良いですが、PythonにはCounter関数があるのでそちらを使った方が簡単かと思います。

なお、両者の違いとしては、

# count:importしなくても使える。各要素の個数を数える。
nums = [2,2,1,1,1,2,2]
print(nums.count(0))
# 0

print(nums.count(1))
# 3

print(nums.count(2))
# 4

#counter:importしないと使えない。出現回数が多い順に要素を取得できる。
from collections import Counter
nums = [2,2,1,1,1,2,2]

num = collections.Counter(nums)

print(num)
# Counter({2: 4, 1: 3})

print(type(c))
# <class 'collections.Counter'>

print(issubclass(type(c), dict))
# True

といったような違いがみられます。今回は過半数を占めるものを返せばいいのでcounterを使って考えます。

from collections import Counter
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        ans =  collections.Counter(nums)
        return ans.most_common(1)[0][0]
#Runtime: 172 ms, faster than 79.63% of Python3 online submissions for Majority Element.
# Memory Usage: 15.1 MB, less than 7.14% of Python3 online submissions for Majority Element.

最初はans.keys()[0]でいけんじゃね？って思ってましたがdictionaryはそれだとエラーになるんですね・・・
なのでCounterに含まれているmost_common()メソッド((要素, 出現回数)という形のタプルを出現回数順に並べたリストを返す)を使ってシンプルに書きました。

良さげな方法が他にあれば追記します。