男女做污的事情网站视频,经典软文,wordpress获取分类名,娄底网站建设方案存在重复元素Ⅱ 问题描述解题思路代码实现复杂度 问题描述
给你一个整数数组 nums 和一个整数 k #xff0c;判断数组中是否存在两个 不同的索引 i 和 j #xff0c;满足 nums[i] nums[j] 且 abs(i - j) k 。如果存在#xff0c;返回 true #xff1b;否则#xff… 存在重复元素Ⅱ 问题描述解题思路代码实现复杂度 问题描述
给你一个整数数组 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)index1print(fmy_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-1u1return False复杂度
时间复杂度O(NLogN)
