こちらは「Contains Duplicate 2」のPythonによる解答例となっております。この問題は、整数の配列と整数kが与えられたとき、配列内に重複する要素があり、その要素のインデックスの間がk以下である場合にTrueを返す問題です。
問題
整数の配列 nums と整数 k が与えられたとき、配列内に重複する要素があり、その要素のインデックスの間がk以下である場合にTrueを返します。
numsには、2つ以上の要素が含まれます。10^5 <= nums.length <= 10^510^9 <= nums[i] <= 10^90 <= k <= 10^5答えは一意に定まります。
解法
この問題には、ハッシュマップを用いた1つのアプローチがあります。アルゴリズムの概要を以下に述べます。
- ハッシュマップを初期化します。
- 配列を1つずつ反復処理します。
- 要素がハッシュマップに存在する場合、そのインデックスと現在のインデックスの差がk以下であるかどうかを確認します。
- 差がk以下である場合、Trueを返します。
- 存在しない場合、現在のインデックスをハッシュマップに追加します。
- 配列の反復処理が終了した場合、重複する要素がないことがわかります。Falseを返します。
Pythonコード
以下のコードが、「Contains Duplicate 2」を解くためのPythonプログラムとなります。
### Function ##################################################################
def solve(num=0):
solver = Solution().containsNearbyDuplicate
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, data.k)
result = "OK" if ans==data.ans else "NG"
print(f"[{str(id).zfill(3)}] {result}")
### Class #####################################################################
class Solution(object):
def containsNearbyDuplicate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
known = {}
for id, num in enumerate(nums):
if num in known:
if id - k <= known[num]: return True
known[num] = id
return False
#==============================================================================
class Input:
def __init__(self, num=0):
if num == 1:
self.nums = [1,2,3,1]
self.k = 3
self.ans = True
elif num == 2:
self.nums = [1,0,1,1]
self.k = 1
self.ans = True
elif num == 3:
self.nums = [1,2,3,1,2,3]
self.k = 2
self.ans = False
else:
self.input = 3
### Main ######################################################################
if __name__ == "__main__":
solve()
###############################################################################