难度: Easy
Submission
运行时间: 20 ms
内存: 16.6 MB
class Solution:
def countElements(self, arr: List[int]) -> int:
m = collections.defaultdict(int)
cont = 0
for i in range(len(arr)):
m[arr[i]] += 1
for num , k in m.items():
if num+1 in m:
cont += k
return cont
Explain
题解采用了哈希表（通过collections.defaultdict实现）来记录数组中每个元素出现的次数。首先，遍历数组arr，利用哈希表m记录每个元素出现的次数。然后，再次遍历哈希表m中的每个元素及其出现次数，检查该元素加1后的值（即num+1）是否也存在于哈希表中。如果存在，说明存在对应的'num+1'元素，此时将当前元素的出现次数累加到结果cont中。最终返回cont，即满足条件的元素总数。
时间复杂度: O(n)
空间复杂度: O(n)
# 定义类和方法
class Solution:
def countElements(self, arr: List[int]) -> int:
m = collections.defaultdict(int) # 使用defaultdict来创建一个默认值为int的哈希表
cont = 0 # 初始化计数器
# 第一次遍历数组，记录每个元素的出现次数
for i in range(len(arr)):
m[arr[i]] += 1
# 第二次遍历哈希表，检查每个元素加1的数是否也在表中
for num, k in m.items():
if num + 1 in m:
cont += k # 如果存在，累加当前元素的计数
return cont # 返回满足条件的元素总数
Explore
哈希表（或字典）提供了平均时间复杂度为O(1)的快速查找、插入和删除操作，这对于本题解中需要频繁查询元素是否存在及其计数的场景非常适合。相比之下，如果使用数组，尽管可以通过索引直接访问元素，但前提是元素的值需要在一个较小的范围内，否则会造成空间浪费或数组大小不够用。使用链表的话，查找或删除一个元素可能需要O(n)的时间复杂度，这在元素数量较大时效率较低。因此，哈希表是处理此类问题的最优数据结构选择。
在哈希表中查找元素的效率高度依赖于哈希函数的质量和冲突解决机制。一个好的哈希函数可以将数据均匀分布在哈希表中，从而减少查找时的冲突概率。为了应对大数据量和提高查找效率，可以采用如链地址法、开放定址法等冲突解决策略。此外，动态调整哈希表的大小（如Python字典在内部实现时所做的）也是保持操作效率的一种常见方法。保证负载因子（即元素个数与哈希表容量的比例）处于合理范围内，也是维持查找效率的关键策略之一。
理论上，哈希表的性能不应该受到其中元素分布的影响，因为哈希表的设计目的就是尽可能减少任何特定数据分布导致的性能下降。在检查元素加1后的存在性时，仍然是常数时间复杂度的操作，因为这依靠的是哈希函数及其冲突解决机制的效率。只要哈希表的实现良好，元素是否均匀分布不会明显影响查找速度。但在实际情况中，如果哈希函数选择不当或冲突过多，可能导致个别操作的性能下降。