算法基础算法

分桶法

字数统计: 1k字   |   阅读时长: 3分
, ,

摘要: 本文总结了 leetcode 上的分桶法相关的题目

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文总结了力扣上 2000 题以内的关于分桶的 14 道题。将场景相同的放到了一起，场景上主要涉及桶排序、平方桶、频率桶、斜率桶、多维桶、哈希桶。数据结构上主要涉及数组、链表、平衡树、哈希表，这些都是主流数据结构，最好都要掌握。刷完这份题目列表，力扣上的分桶的问题可以说刷爆了。

分桶法是把一排元素(key)按照某种标准放到各个桶中，每个桶分别维护自己内部的信息，外部只需要管理各个桶即可，提高计算的效率。

分桶的思想类似于公司等大型组织的管理方式: 由于公司太大了，高管根本管不过来，于是就分了很多的部门，然后部门各自管理自己内部的事情，高管只需要管理各个部门而不插手部门内部的事情就可以实现全局的管理。

根据需求实现桶的数据结构可以有很多，常见的有: vector, 链表, map, unordered_map，桶内元素也可以用各种数据结构维护，也可以是另一个桶。

桶排序

桶的数量可控的时候，桶结构可以用于实现排序算法。如果每个数字都是一个桶，就变成了计数排序。

力扣164-最大间距 是桶排序的经典题。

除此之外，非比较排序 中整理了桶排序和计数排序的题目汇总和题解。

平方桶

平方分桶是把排成一排的 n 个元素每 $\sqrt{n}$ 个分在一个桶内进行维护的方法的统称。这样的分桶方法可以使对区间的操作的复杂度降至 $O(\sqrt{n})$。

在 力扣1157-分块查找表,无修改区间众数 中解决了一个无修改的区间众数的问题，基于平方分桶的分块查找表是众多方法中比较容易实现的一种。

频数桶

将 key 的查询次数作为给 key 分桶的依据。在 【频数分桶】力扣1224-最大相等频率 中解决了一个基于频数分桶的问题，并且对基于数组的桶和基于链表的桶都做了实现。

力扣460-LFU，【设计难题】力扣895-最大频率栈 和 【设计难题】力扣432-全O(1)的数据结构 是设计带有频数分桶需求的数据结构的问题。它们的基础结构都可以抽象为 邻接表。

斜率桶

在计算几何问题中，很多时候要把直线按照斜率排序后处理，但是斜率相同的情况又有特殊的处理逻辑。这时候需要把直线按照斜率分桶处理，实现桶的数据结构一般是 TreeMap。

哈希桶

用哈希函数对不同的 key 求哈希值，可能会出现冲突的情况。那么对于同一哈希值的不同 key 可以通过桶的方式维护，开散列表就是这么做的。【模板】哈希集合 和 【模板】无重哈希映射 这两篇文章在开散列表的基础上实现了有重和无重的哈希集合和无重哈希映射。

多维桶

对 key 有多个分桶条件。

Share