こちらは「Contains Duplicate」のPythonによる解答例となっております。この問題は、整数の配列が与えられたとき、重複する要素があるかどうかを判断する問題です。
問題
整数の配列 nums が与えられたとき、配列内に重複する要素がある場合は True を、そうでない場合は False を返します。
1 <= nums.length <= 10^510^9 <= nums[i] <= 10^9答えは一意に定まります。
解法
この問題は、Pythonのsetを用いた1つのアプローチがあります。setは、重複する要素を保持せず、検索を高速化するため、この問題に適しています。
アルゴリズムの概要を以下に述べます。
- 配列
numsをsetに変換します。 - 配列
numsの要素数とsetの要素数を比較します。 - 2つの数値が異なる場合、重複する要素があることを示す
Trueを返します。 - 2つの数値が同じ場合、重複する要素がないことを示す
Falseを返します。
Pythonコード
以下のコードが、「Contains Duplicate」を解くためのPythonプログラムとなります。
### Function ##################################################################
def solve(num=0):
solver = Solution().containsDuplicate
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 containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
return len(nums) != len(set(nums))
#==============================================================================
class Input:
def __init__(self, num=0):
if num == 1:
self.nums = [1,2,3,1]
self.ans = True
elif num == 2:
self.nums = [1,2,3,4]
self.ans = False
elif num == 3:
self.nums = [1,1,1,3,3,4,3,2,4,2]
self.ans = True
else:
self.input = 3
### Main ######################################################################
if __name__ == "__main__":
solve()
###############################################################################