动手刷力扣第五天 |
您所在的位置：网站首页 › 卡盟qq刷 › 动手刷力扣第五天 |
动手刷力扣第五天
|
哈希表是根据关键码值(Key value)而直接进行访问的数据结构。在python中表现为字典。 下面我们讨论一下哈希表的搜索，插入，删除等操作。（哈希表不存在访问操作） 哈希表的搜索，插入与删除：在没有哈希碰撞的前提下，哈希表的搜索只需要找到key，即可得到其对应的value，所以时间复杂度是O(1)。有哈希碰撞的情况，则为O(k)，k为碰撞的元素的个数。 哈希表的插入如删除也是通过key来操作的，时间复杂度都是O(1)。 下面是python中常用的哈希表操作： # create hashtable by dictionary mapping = {} # add element time complexity：O(1) mapping[1] = 'lihua' mapping[2] = 'liming' mapping.[3] = 'lilei' # update element time complexity:O(1) mapping[1] = 'bishi' # remove element time complexity:O(1) temp = mapping.pop(1) print(temp) # bishi # get value time complexity:O(1) print(mapping[3]) # lilei # get size size = len(mapping) print(size) # 2 熟悉了哈希表的相关操作后我们来看看对应的简单题。力扣217存在重复元素：
对于这道题，我们定义一个哈希表（字典），在对数组进行遍历，第一次出现的数我们把对应的value记为1，后面再出现一次value的值就+1，最后我们只需查看哈希表里的value的值是否有大于1的即可。 class Solution: def containsDuplicate(self, nums: List[int]): if len(nums) == 0 and len(nums) == 1: return False ht = {} for i in nums: # 遍历整个数组 if i not in ht: # 如果取出来的数不在哈希表里面，就把他存进去，value=1 ht[i] = 1 else: # 如果已经存在了，取出value的值+1 ht[i] = ht.get(i) + 1 for j in ht.values(): # 看看在哈希表里面的值是否大于1即可 if j > 1: return True return False # time complexity: O(N) 遍历数组，两个for循环并列 # space complexity：O(N) 产生了新的数据结构 力扣389找不同：
对于这道题，我们采用了一种取巧的方式，建立一个初始为26个0的哈希表，当某个字母在s中出现一次时，对应的字母的value -1，在t中出现时+1，这样两者都有的字母还是为0，这样我们再去寻找哈希表中value不为0的key，对应的字母则为t比s多的字母。 class Solution: def findTheDifference(self, s: str, t: str): if len(s)==0: # 如果s为空，直接返回比s多一个元素的t即可 return t table=[0]*26 for i in s: table[ord(i)-ord('a')] = table[ord(i)-ord('a')]-1 # s中每个符号的ascii值化为0，每出现一次-1 for j in t: table[ord(j)-ord('a')] = table[ord(j)-ord('a')]+1 # t中每个符号的ascii值化为0，每出现一次+1 # 这样t中多的一个元素的value就是1其他都互相抵消，是0 for k in range(26): if table[k] != 0: # 找出value=1的key，这是他的ascii值-97（刚刚化为0减的） return chr(k+97) # 加回97再转化为字符就可以了 return # time complexity：O(N) # space complexity：O(1) 力扣496下一个更大元素：
这道题我们在前面栈的学习中做过一次，当时我们所用的时间复杂度是O(MN)，现在我们来看看使用哈希表的做法。首先遍历nums2，把他的元素依次放在栈里。每取一个数时将他与栈顶元素对比，如果比栈顶元素小，那么继续存进栈里面，如果比栈顶元素大，那么他就是目前栈里面的元素色下一个比x大的数，将他们都取出作为哈希表的key，value为新取的这个数，即前面这几个元素的下一个比x大的数（说的比较抽象，可以画图帮助理解）。如果没有下一个比x大的数，即保存到哈希表中，value为-1，最后遍历nums1，返回其key值对应的value值即可。for循环分别遍历了nums1和nums2，时间复杂度为O(M+N) class Solution: def nextGreaterElement(self, nums1: List[int], nums2: List[int]): RES = [] stack = [] ht = {} for i in nums2: while len(stack) !=0 and i>stack[-1]: # 当存进去的数大于栈顶元素，就是下一个比x大的数 temp = stack.pop() # 把栈里比新取的数小的数挨个取出来加到哈希表的key里去 ht[temp] = i # i放到哈希表的value，也就是前面的key对应的下一个比x大的数 stack.append(i) # 把num2一个个存进栈里面 # for循环结束，已经找到num2里面每个元素的下一个比x大的元素 while(len(stack) != 0): # 如果栈里还有元素，就是没有下一个比x大的元素，赋值-1 ht[stack.pop()] = -1 # 取出来的数放在key，-1放在value for i in nums1: # 遍历num1，在哈希表里查找下一个比x大的值返回给RES即可 RES.append(ht[i]) return RES # time complexity:O(M+N) # space complexity:O(N) |
【本文地址】
今日新闻 |
推荐新闻 |