代码训练(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^9
- 0 <= 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 = 0，nums[i] = 1，map 更新为 {1: 0}。
- i = 1，nums[i] = 2，map 更新为 {1: 0, 2: 1}。
- i = 2，nums[i] = 3，map 更新为 {1: 0, 2: 1, 3: 2}。
- i = 3，nums[i] = 1，发现 1 已存在，且 abs(3 - 0) = 3，满足条件，返回 true。
性能优化关键点：
- 哈希表的使用：通过使用哈希表来快速查找和更新元素索引，复杂度为 O(1)。
- 一次遍历：只需要遍历一次数组，时间复杂度为 O(n)，其中 n 是数组的长度。
3. 代码实现
#include
#include #include bool 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 indices if (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) 内，适合处理大规模数据。