物以类聚，数以"桶"分
"桶"在数据结构与算法领域可以说是有着重要的应用，从简单的排序算法到某些特定数据结构，运用桶的思想考虑问题往往有出人意料的效果。
结合最近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
运用桶的思想，时间复杂度一般可实现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 结论
桶的思想在数据结构与算法中有着灵活和广泛的运用，常常在面对具有区间比对和相近结构等特点的问题时，可优先考虑能否借助桶来实现。
当然，严格的讲桶并不是一种算法，而只能称作是一种数据处理的思路和方法，运用得当会十分高效。
可能它无法独当一面，但至少能够左右逢源！