当前位置 博文首页 > 峰峰的猫的博客:查找之哈希表(python实现LeetCode刷题)
根据数据结构书上的讲解,查找包括暴力遍历、折半查找以及二叉树查找。其中顺序查找和折半查找适合静态查找,折半查找前提线性表必须是有序的。三种查找算法的时间复杂度分别是 O ( n ) , O ( l o g n ) , O ( l o g n ) O(n),O(logn),O(logn) O(n),O(logn),O(logn)。线性表和树表都是通过比较关键字的方法,查找的效率取决于关键字的次数。有没有一种方法可以不进行关键字比较,直接找到目标?那就是散列表的查找,也称哈希表。是通过散列函数将关键字映射到存储地址,建立了关键字和存储地址的一种直接映射关系。
这里主要讲解python中dict使用的哈希表,最低能在
O
(
1
)
O(1)
O(1)时间内完成搜索!python中dict在处理冲突的时候采用的是开放寻址法,开放寻址法是在线性存储空间上的解决方案,也称为闭散列。当发生冲突时,采用冲突处理方法在线性存储空间上探测其他位置:
h
a
s
h
,
(
k
e
y
)
=
(
h
a
s
h
(
k
e
y
)
+
d
i
)
hash^,(key) = (hash(key)+d_i)%m
hash,(key)=(hash(key)+di?)
开放寻址法又分为线性探测法、二次探测法、随机探测法和再散法。
注意:开放地址法处理冲突时,不能随便删除表中的元素,若删除元素会截断其他后续元素的查找。因为在查找过程中,遇到空就会返回查找失败,因此要删除一个元素式,可以做一个删除标记,表示该元素已经删除。
该题链接:https://leetcode-cn.com/problems/contains-duplicate/
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
t_dict = {}
for num in nums:
if num not in t_dict.keys():
t_dict[num] = 1
else:
return True
return False
cs