网站建设规范方法,企业解决方案架构,网站seo优化要懂得做微调,网页设计代码爱心代码训练(17)LeetCode之存在重复元素
Author: Once Day Date: 2024年5月7日
漫漫长路#xff0c;才刚刚开始…
全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客
参考文章:
219. 存在重复元素 II - 力扣#xff08;LeetCode#xff09;力扣 (LeetCode) 全球…代码训练(17)LeetCode之存在重复元素
Author: Once Day Date: 2024年5月7日
漫漫长路才刚刚开始…
全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客
参考文章:
219. 存在重复元素 II - 力扣LeetCode力扣 (LeetCode) 全球极客挚爱的技术成长平台 文章目录 代码训练(17)LeetCode之存在重复元素1. 原题2. 分析3. 代码实现4. 总结 1. 原题 给你一个整数数组 nums 和一个整数 k 判断数组中是否存在两个 不同的索引 i 和 j 满足 nums[i] nums[j] 且 abs(i - j) k 。如果存在返回 true 否则返回 false 。 1 nums.length 10^5-10^9 nums[i] 10^90 k 10^5 例如对于nums [1,2,3,1,2,3], k 2不存在间隔两个以内的相等值因此返回False。
2. 分析
该题目要求我们判断一个给定的整数数组 nums 中是否存在两个不同的索引 i 和 j使得 nums[i] nums[j] 且两个索引的差的绝对值不大于 k。如果存在这样的一对索引则返回 true否则返回 false。
要解决这个问题可以采用哈希表记录法
创建一个哈希表来存储数组值和其对应的最新索引。遍历数组对于每个元素检查哈希表中是否已经存在该元素 如果存在则比较当前索引与哈希表中存储的索引的差的绝对值是否不大于 k。如果满足条件则直接返回 true。如果不满足条件或者元素不存在于哈希表中则更新哈希表将该元素的索引设置为当前索引。 如果遍历完数组后没有找到符合条件的元素对则返回 false。
分析步骤
初始化一个空的哈希表 map。遍历数组 nums对于每个元素 nums[i] 检查 nums[i] 是否已存在于 map 中。如果存在计算当前索引 i 和 map[nums[i]] 的差的绝对值。如果这个差值小于等于 k返回 true。否则更新 map[nums[i]] 为当前索引 i。 遍历结束后如果没有找到符合条件的索引对返回 false。
举例分析以 nums [1,2,3,1], k 3 为例
初始化 map {}。遍历 nums i 0nums[i] 1map 更新为 {1: 0}。i 1nums[i] 2map 更新为 {1: 0, 2: 1}。i 2nums[i] 3map 更新为 {1: 0, 2: 1, 3: 2}。i 3nums[i] 1发现 1 已存在且 abs(3 - 0) 3满足条件返回 true。
性能优化关键点
哈希表的使用通过使用哈希表来快速查找和更新元素索引复杂度为 O(1)。一次遍历只需要遍历一次数组时间复杂度为 O(n)其中 n 是数组的长度。
3. 代码实现
#include stdbool.h
#include stdio.h
#include stdlib.hbool containsNearbyDuplicate(int* nums, int numsSize, int k) {int* map (int*)calloc(200001, sizeof(int));for (int i 0; i numsSize; i) {int num nums[i] 100000; // Offset to handle negative indicesif (map[num] ! 0 i - (map[num] - 1) k) {free(map);return true;}map[num] i 1; // Store index 1 to distinguish from initial zero}free(map);return false;
}int main() {int nums[] {1, 2, 3, 1};int k 3;int numsSize sizeof(nums) / sizeof(nums[0]);bool result containsNearbyDuplicate(nums, numsSize, k);printf(Result: %s\n, result ? true : false);return 0;
}这段代码实现了一个函数 containsNearbyDuplicate用于检查给定的整数数组 nums 中是否存在两个相同的元素它们的下标之差的绝对值小于等于 k。
代码使用了哈希表的思想来优化查找效率。哈希表的大小为 HashSize定义为 0x1fff 1即 8192。哈希表使用链表法解决哈希冲突每个哈希桶都是一个链表的头节点。
函数 hash_reset 用于重置哈希表释放所有节点的内存。
函数 containsNearbyDuplicate 的主要步骤如下
重置哈希表。遍历数组 nums对于每个元素 计算哈希索引 nums[i] 0x1fff即将元素的低 13 位作为哈希索引。在对应的哈希桶中查找是否存在相同的元素且下标之差的绝对值小于等于 k如果找到则返回 true。如果没有找到则创建一个新的节点存储当前元素的值和下标插入到哈希桶的链表中。 如果遍历完整个数组都没有找到符合条件的元素对则返回 false。
运行结果如下所示(仅供参考): 这段代码写得很暴力优化空间很大:
哈希表的大小 HashSize 可以根据实际情况进行调整选择一个合适的大小以平衡内存使用和哈希冲突的概率。可以考虑使用更高效的哈希函数例如使用素数取模或者其他哈希算法以减少哈希冲突的概率。在插入新节点时可以先判断链表的长度是否超过了一定的阈值如果超过了可以考虑将链表转换为其他数据结构如红黑树以提高查找效率。可以考虑在插入新节点时如果链表长度超过了 k则可以直接删除链表头部的节点因为它们的下标之差肯定大于 k不会影响结果。
4. 总结
本题主要考查对数组遍历和哈希表的应用能力。通过使用哈希表存储元素的最新索引我们能够有效检查是否有符合条件的索引对。这种方法利用了哈希表快速查找和插入的特性使得时间复杂度控制在 O(n) 内适合处理大规模数据。
