"桶"在数据结构与算法领域可以说是有着重要的应用,从简单的排序算法到某些特定数据结构,运用桶的思想考虑问题往往有出人意料的效果。
结合最近LeetCode几个原题,总结几个应用桶的例子。
01 桶排序算法
首先,回顾下经典的桶排序算法。
桶排序中,根据一定规则对待排序的大量数据进行宏观划分,实现了大体上的排序,保证桶与桶之间的数据是有序的。桶内部的数据需要二次排序,可以递归对各个桶内的小规模数据再次进行分桶,也可以调用其他排序算法实现。
当然,这里的桶的个数和分桶的方式有很多讲究:好的分桶规则可以最大化快速实现排序;反之,分桶过于集中、稀疏或者不均衡,都会带来时间或者空间效率上的降低。
桶排序实现案例:
def bucket_sort(lyst):
n = max(10, len(lyst)//10)#设置至少10个、最多len/10个桶,此时平均每个桶中10个元素
minNum = min(lyst)
d = (max(lyst) - minNum+1)/n
buckets = {i:[] for i in range(n)}
for num in lyst:
index = int((num-minNum)/d)##取整得到桶标号
buckets[index].append(num)
lyst[:] = [num for i in range(n) for num in sorted(buckets[i])]
不失一般性,各桶调用内置函数实现二次排序
特殊情况下,当桶的个数与待排序数据跨度(最大值-最小值)一致时,则是计数排序;当分桶的规则设计为按数据逐位比较时,则是基数排序。所以,计数排序和基数排序都可以看做是桶排序的一个特例。
与计数和基数排序算法效率一致,桶排序有着线性阶复杂度,而又有前两者所不具备的应用一般性,例如需对浮点数排序时。
02 数值排序类
应用桶排序,可以实现很多排序类问题的求解。
题目1:
给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。如果数组元素个数小于 2,则返回 0。 示例 1: 输入: [3,6,9,1] 输出: 3 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。 要求:
来源:力扣(LeetCode)164# 最大的间距
显然,题目已经给出明确暗示,要求在线性时间和空间复杂度下完成求解。那么所有的比较型排序算法无法满足。
由于所有元素都是非负整数,所以计数、基数和桶排序算法都可以应用。但计数可能会因排序数据跨度范围较大而存在空间溢出的问题,为此我们选用桶排序予以解决。
案例源码:
def maximumGap(self, nums: List[int]) -> int:
if len(nums)<2:
return 0
def bucket_sort(lyst):
n = max(10, len(lyst)//10)#设置至少10个、最多len/10个桶,此时平均每个桶中10个元素
minNum = min(lyst)
d = (max(lyst) - minNum+1)/n
buckets = {i:[] for i in range(n)}
for num in lyst:
index = int((num-minNum)/d)##取整得到桶标号
buckets[index].append(num)
lyst[:] = [num for i in range(n) for num in sorted(buckets[i])]
bucket_sort(nums)
gap = 0
for index in range(1, len(nums)):
if nums[index] - nums[index-1]>gap:
gap = nums[index] - nums[index-1]
return gap
当然,本题比较中规中矩,尚不足以体现桶的魔力。
题目2:
给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的绝对值最大为 k。 示例 1: 输入: nums = [1,2,3,1], k = 3 输出: true 来源:力扣(LeetCode)219# 存在重复元素 II
本题不能直接运用桶排序,至少是在不构造其他数据结构的情况下不能使用排序算法,否则会失去原有的索引信息。
注:若一定要用排序算法也是可以的,比如对每个元素构造(index,num)元组,并以元组第二个值为key进行排序,然后判断是否存在同数值下是否存在两个index满足要求即可。
不能直接对数据进行排序,但可以运用桶的思想做些尝试。
设计桶的规则如下:
基于以上的桶规则,可以实现问题求解。当然,具体到本题,实际上每个桶内无需存储满足该数值的全部索引信息,而最多存储相近的两个索引就足够判断。
更进一步的,甚至不需要存储两个索引信息,在顺序遍历原列表的情况下,只存储该数值的最近一个索引即可:当遇到该数值的一个新索引时,若与已存储的前一个索引相差满足要求,则返回True值;否则用新索引替代原索引来与后面可能的其他索引比较。
至此,这里的桶实际上已退化为更一般的字典数据结构:数值-索引对。
虽然最后解决问题依靠的是字典,但分析的过程其实蕴含了很深的桶思想。
案例源码:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
buckets = {}
for index, num in enumerate(nums):
if num in buckets and abs(buckets[num] - index)<=k:
return True
else:
buckets[num] = index
return False
题目3:
给定一个整数数组,判断数组中是否有两个不同的索引 i 和 j,使得 nums [i] 和 nums [j] 的差的绝对值最大为 t,并且 i 和 j 之间的差的绝对值最大为 ķ。 示例 1: 输入: nums = [1,2,3,1], k = 3, t = 0 输出: true 示例 2: 输入: nums = [1,0,1,1], k = 1, t = 2 输出: true 示例 3: 输入: nums = [1,5,9,1,5,9], k = 2, t = 3 输出: false 来源:力扣(LeetCode)220# 存在重复元素 III
与前一题不同,本题无法继续应用字典数据结构实现解答。但有了之前的分析过程,再运用桶的思想就比较自然。
由于要求在数值相差小于t的情况下来判断索引差值,我们仍然设计一个用于存储元素索引的桶,但桶的大小不再是1(上题中的退化字典结构),而是一个涵盖区间为t的桶。理由是对可能满足数值相差小于t的两个目标对象,要么在同一桶中,要么在相邻桶中,其余情况相差肯定大于t。
由于遍历原数组时,只判断或赋值当前桶的索引,而判断时却要考虑相邻两个桶中的数值,所以就必须考虑同步更新所有桶中索引信息。
另外,为了兼顾t取值为0的特殊情形(上题中的两值相等),我们考虑桶的最小区间为1,此时再次退化为计数排序。
案例源码:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
if not nums or not k or t<0:
return False
buckets = {}
for index, num in enumerate(nums):
p = num//max(1, t)
if p in buckets or (p-1 in buckets and abs(buckets[p-1]-num)<=t) or (p+1 in buckets and abs(buckets[p+1]-num)<=t):
return True
else:
buckets[p] = num
if len(buckets)>k:
buckets.pop(nums[index-k]//max(1, t))
return False
运用桶的思想,时间复杂度一般可实现O(n)
03 字符串应用
除了数组的区间处理,在字符串的一些应用中,也可以考虑运用桶的思想来实现某些规则下的匹配问题。
题目1:
给定两个单词(beginWord 和 endWord)和一个字典,找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则: 每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 示例 1: 输入: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] 输出: 5 来源:力扣(LeetCode)127#单词接龙
这里,要寻找的是一条从beginWord到endWord的接龙词,要求相邻词之间仅有一个字母不同。有一个字母不同,就意味着其他字母都相同,那么满足相邻规则的单词之间实际上就存在了某种联系,进而可以构建不同的桶加以区别。
这里,桶的规则自然就是相差小于一个字符。
如果直接判断两个单词是否相差1个字符,那么无异于暴力算法的字符串比较。类似正则表达式,构建一个通配符来实现单词匹配和桶的划分:"hot"、"dot"和"lot"都可以分在同一桶"_ot"中,"dot"和"dog"又可以划分在另一个桶"do_"中。划分在同一桶中的所有单词,必然是相差字符为1的单词,进而可以构成结果序列中的相邻词。
在完成所有可能相邻词的分桶后,运用广度优先进行遍历即可,期间同步记录遍历深度。一旦找到目标单词endWord,即返回结果,广度优先搜索的具体实现这里不再展开。
案例源码:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
wordList.append(beginWord)
##### 构建匹配桶
buckets = collections.defaultdict(list)
for word in wordList:
for i in range(len(beginWord)):
match = word[:i]+'_'+word[i+1:]
buckets[match].append(word)
toSeen = collections.deque([(beginWord, 1)])
befound = {beginWord:1}
#####BFS遍历
while toSeen:
cur, level = toSeen.popleft()
for i in range(len(beginWord)):
for word in buckets[cur[:i]+'_'+cur[i+1:]]:
if endWord == word:
return level+1
if word not in befound:
befound[word] = level+1
toSeen.append((word, level+1))
return 0
题目2:
给定两个单词(beginWord 和 endWord)和一个字典 wordList,找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则:每次转换只能改变一个字母。转换过程中的中间单词必须是字典中的单词。 示例 1: 输入: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] 输出: [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ] 来源:力扣(LeetCode)126# 单词接龙II
相比前一题,唯一区别在于前者所求为最小深度,本题所求为最小深度下的所有解。
题外话:一般来讲,求解最小深度要用广度优先,求所有解要用回溯。 但本题的所有解是在最小深度情况下的所有解,所以不能简单的用递归回溯作答。
接续上一题中桶的思想,只不过是这一次不再是浅尝辄止,而是要在找到目标后仍然把当前深度遍历完全,直至搜索深度超过已找到目标单词的深度。
只需稍微改变下数据结构,构造一个前溯词字典列表的数据结构即可实现。具体不再赘述。
案例源码:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
wordList.append(beginWord)
buckets = collections.defaultdict(list)
for word in wordList:
for i in range(len(beginWord)):
match = word[:i]+'_'+word[i+1:]
buckets[match].append(word)
pres = collections.defaultdict(list)#前溯节点
toSeen = collections.deque([(beginWord, 1)])
befound = {beginWord:1}
#####BFS遍历
while toSeen:
cur, level = toSeen.popleft()
for i in range(len(beginWord)):
for word in buckets[cur[:i]+'_'+cur[i+1:]]:
if word not in befound:
befound[word] = level+1
toSeen.append((word, level+1))
if befound[word] == level+1:
pres[word].append(cur)#记录前溯节点
if endWord in befound and level+1 > befound[endWord]:
break
if endWord in befound:
res = [[endWord]]
while res[0][0] != beginWord:
res = [[word]+r for r in res for word in pres[r[0]]]
return res
else:
return []
需要指出,解决这两题的关键仍然在于BFS的运用,但借助桶的思想可以巧妙完成单词的预处理。相比纯粹的字符串暴力比较算法,利用桶的单词分组方式可有效提高效率。
04 结论
桶的思想在数据结构与算法中有着灵活和广泛的运用,常常在面对具有区间比对和相近结构等特点的问题时,可优先考虑能否借助桶来实现。
当然,严格的讲桶并不是一种算法,而只能称作是一种数据处理的思路和方法,运用得当会十分高效。
可能它无法独当一面,但至少能够左右逢源!