写一段代码,尽量降低时间复杂度,给定n个不同的整数,问这些数中有多少对整数,它们的值正好相差1。
时间: 2024-03-23 20:38:25 浏览: 114
数据结构快速排序基本算法
好的,以下是一个时间复杂度为O(n)的 Python 代码,可以解决你提出的问题:
```python
def count_pairs(arr):
"""
给定一个整数数组,返回其中的一对数值正好相差1的数的数量。
"""
count = 0
num_set = set(arr)
for num in num_set:
if num+1 in num_set:
count += 1
return count
```
这个算法的时间复杂度为O(n),它利用了set数据结构的快速查找特性,对于每个数只需要判断它的后继是否在集合中即可。
阅读全文