"桶"在数据结构与算法领域可以说是有着重要的应用,从简单的排序算法到某些特定数据结构,运用桶的思想考虑问题往往有出人意料的效果。
结合最近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。
要求:
- 你可以假设数组中所有元素都是非负整数,且数值在 32 位有符号整数范围内。
- 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
来源:力扣(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满足要求即可。
不能直接对数据进行排序,但可以运用桶的思想做些尝试。
设计桶的规则如下:
- 以每个数值为标签建立一个桶
- 桶内的存储元素为该数值的索引信息
- 该桶仅能回溯至倒数第k个索引
基于以上的桶规则,可以实现问题求解。当然,具体到本题,实际上每个桶内无需存储满足该数值的全部索引信息,而最多存储相近的两个索引就足够判断。
更进一步的,甚至不需要存储两个索引信息,在顺序遍历原列表的情况下,只存储该数值的最近一个索引即可:当遇到该数值的一个新索引时,若与已存储的前一个索引相差满足要求,则返回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
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 结论
桶的思想在数据结构与算法中有着灵活和广泛的运用,常常在面对具有区间比对和相近结构等特点的问题时,可优先考虑能否借助桶来实现。
当然,严格的讲桶并不是一种算法,而只能称作是一种数据处理的思路和方法,运用得当会十分高效。
可能它无法独当一面,但至少能够左右逢源!