こちらは「Majority Element」のPythonによる解答例となっております。この問題は、長さnの配列numsが与えられたとき、出現回数がn/2を超える要素を返す問題です。
問題
長さnの配列 nums が与えられたとき、出現回数がn/2を超える要素を返します。
numsは長さが1以上の整数の配列です。3 <= n <= 5*10^42^31 <= nums[i] <= 2^31 - 1
解法
この問題は、ソートを用いた1つのアプローチがあります。出現回数がn/2を超える要素は必ず存在するため、配列をソートした後にnums[n/2]を返すことができます。
アルゴリズムの概要を以下に述べます。
- 配列をソートします。
- nums[n/2]を返します。
Pythonコード
以下のコードが、「Majority Element」を解くためのPythonプログラムとなります。
### Function ##################################################################
def solve(num=0):
solver = Solution().majorityElement
if 1 <= num <= Input().input: id_LIST = [num]
else: id_LIST = [id+1 for id in range(Input().input)]
for id in id_LIST:
data = Input(id)
ans = solver(data.nums)
result = "OK" if ans==data.ans else "NG"
print(f"[{str(id).zfill(3)}] {result}")
### Class #####################################################################
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
return nums[len(nums)//2]
# def majorityElement(self, nums):
# """
# :type nums: List[int]
# :rtype: int
# """
# DICT = {}
# for val in nums:
# if val not in DICT: DICT[val] = 1
# else: DICT[val] += 1
# return [key for key, val in DICT.items() if val==max(DICT.values())][0]
#==============================================================================
class Input:
def __init__(self, num=0):
if num == 1:
self.nums = [3,2,3]
self.ans = 3
elif num == 2:
self.nums = [2,2,1,1,1,2,2]
self.ans = 2
else:
self.input = 2
### Main ######################################################################
if __name__ == "__main__":
solve()
###############################################################################