どーも！
たかぽんです！
今日もやっていきます！
217. Contains Duplicate
今回の問題は以下。
最近似ている物ばかりではありますが...w
配列に重複があれば。trueを、なければfalseを返す...という至って簡単なものです。
例をお借りすると...
# 例1
Input: [1,2,3,4]
Output: false
# 例2
Input: [1,2,3,1]
Output: true上記のような感じです。
では、早速次はアルゴリズム検討してみます...!
アルゴリズム
最初は配列の要素を取り出し、その要素が取り出した後の配列に含まれているかどうかを判定する...といった形で考えていたのですが...
以下ではタイムオーバーでした...
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
inputLength = range(len(nums))
for num in inputLength:
num = nums[0]
nums.pop(0)
if num in nums:
return 1
return 0
と、いうわけで、別の方法を考えたのですが、いったんソートをすれば、同じ要素が隣同士になる...と言うことを利用して、ソート後に隣り合う要素を比較して比較を行う...といった形で考えました。
rangeを使って、配列長分繰り返しを行い、2要素を比較する際にout of rangeにならないよう、0ではなく、1から開始しました。
そしてどこでもいいので、横並びの二つの値が等しい場合があれば、それは重複がある...ということなので、1を。
そうでない（forを抜けた場合）は0を返せば良さそうです。
計算量の比較はあまり把握はできていないんですが...
前者だとforで配列長分 * num in numsでさらに配列長分...?(Nの二乗ですかね...?)
後者だと少なくともN-1かな？（そのうちしっかり勉強してきます...orz)
ぼちぼちしっかりと計算量も意識していかないといけなさそうですね...!
最後に、僕が提出したコードを貼っておきます。
提出したコード
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
nums.sort()
for i in range(1,len(nums)):
if nums[i] == nums[i-1]:
return 1
return 0
#以下、結果
Runtime: 120 ms, faster than 63.92% of Python3 online submissions for Contains Duplicate.
Memory Usage: 19.3 MB, less than 88.13% of Python3 online submissions for Contains Duplicate.