存在重复元素Ⅱ python3

问题描述

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：
输入：nums = [1,2,3,1], k = 3
输出：true

示例 2：
输入：nums = [1,0,1,1], k = 1
输出：true

示例 3：
输入：nums = [1,2,3,1,2,3], k = 2
输出：false

解题思路

哈希表结构，key存储数字，value存储该数字出现的索引，且value为列表结构。若当前数字对应的列表长度大于2，则表明至少存在相同的两个索引，使得nums[i] == nums[j]，将此列表降序排列，一一比较，如存在i-j小于等于k则返回True。

代码实现

def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:my_dict ={}index = 0for num in nums:if num not in my_dict.keys():my_dict.setdefault(num,[]).append(index)else:my_dict[num].append(index)index+=1print(f"my_dict:{my_dict}")keys = my_dict.keys()for i in keys:if len(my_dict[i])>=2:sorted_dict_list = sorted(my_dict[i], reverse = True)n = len(my_dict[i]) u = 0while u <n:j = n-1while j >u:if sorted_dict_list[u]-sorted_dict_list[j]<=k:return Trueelse:j-=1u+=1return False

复杂度

时间复杂度：O(NLogN)