← 返回编程题库
coding-bucket-sort-pnl-quantiles简单免费版2000ms未尝试

桶排序构建盈亏直方图

Bucket-Sort P&L Histogram

开始编码

风控看板每隔几秒就要重画一次「日内盈亏直方图」:拿到几千个仓位的逐仓 mark-to-market 盈亏,把每个数扔进对应的桶里,再渲染成柱状图。桶网格由风控团队固定下来——下界 lo、上界 hi、桶数 n_buckets,由风险偏好决定(例如 lo = -1e6, hi = 1e6, n_buckets = 200,紧盯 ±$1M 区间)。落在 [lo, hi) 之外的值要裁到边界桶不是丢掉——一笔 $5M 的尾部亏损之所以重要,恰恰是因为它把最左侧的柱子顶满。

请实现 solution(values: list[float], lo: float, hi: float, n_buckets: int) -> list[int]。返回长度为 n_buckets 的列表,第 i 个元素是落入桶 i 的值的个数。桶编号公式:idx = floor((v - lo) / width),其中 width = (hi - lo) / n_buckets,最后裁到 [0, n_buckets - 1]。边界:v == lo → 桶 0;v == hi → 桶 n_buckets - 1(原始 idx 是 n_buckets,被裁回去)。调用方保证 lo < hi(零宽或负宽桶没有定义)。

示例solution([-3.0, -1.0, 0.0, 1.0, 3.0], -5.0, 5.0, 5) 返回 [0, 1, 2, 1, 1]。桶区间为 [-5,-3), [-3,-1), [-1,1), [1,3), [3,5]。五个输入分别落到 1、2、2、3、4。再看裁剪:solution([100.0, 200.0, -100.0], 0.0, 10.0, 5) 返回 [1, 0, 0, 0, 2]——那个负值把最左桶顶满,两个大正值都被裁到最右桶。再看退化的一桶情形:solution([0.5, 0.7, 0.9], 0.0, 1.0, 1) 返回 [3]n_buckets = 1 时所有值(无论在不在区间内)都进桶 0。

朴素思路是把数组排序再数连续段,复杂度 O(n log n)。桶排序换一种思路——每个元素只用 O(1) 的算术运算定位到所属桶,元素之间没有任何比较,总代价 O(n + k)k = n_buckets)。这种线性时间保证,正是风控系统能在两次心跳之间把百万仓位重新分桶的关键。这一套手法是通用的:compute index → bump counter 的模式同样支撑着 counting sort、radix sort,以及 numpy / pandas / GPU 核里的 histogram 原语。

约束条件

  • 0 ≤ len(values) ≤ 100000
  • lo < hi(严格小于的前置条件;端点相等意味着零宽度桶——由调用方保证)
  • 1 ≤ n_buckets ≤ 1000
  • values 是浮点数;桶计数是整数(无浮点误差容忍)
  • 越界值裁到最近的桶:`v < lo` 进桶 0,`v >= hi` 进桶 `n_buckets - 1`

样例

Case 1 · uniform spread across 5 buckets

输入: [[-3,-1,0,1,3],-5,5,5]

期望: [0,1,2,1,1]

区间 [-5, 5] 等分为 5 个宽度为 2 的桶:[-5,-3), [-3,-1), [-1,1), [1,3), [3,5]。按 idx=floor((v-lo)/width) 计算,-3 落桶 1,-1 落桶 2,0 落桶 2,1 落桶 3,3 落桶 4。注意 3.0 算出 idx=4(恰好在右开端点),不需要裁剪。

Case 2 · all out of range — clip both sides

输入: [[100,200,-100],0,10,5]

期望: [1,0,0,0,2]

区间 [0, 10] 五桶。-100 在下界外裁到桶 0;100、200 都在上界外裁到桶 4。最终 [1,0,0,0,2]。题目规则:v < lo 进桶 0,v >= hi 进桶 n_buckets-1。

Case 3 · n_buckets=1 — everything in one bucket

输入: [[0.5,0.7,0.9],0,1,1]

期望: [3]

n_buckets=1 时整个 [lo, hi] 区间只有一个桶。任何输入(包括越界)都会被裁到桶 0。这里三个值均落入桶 0,结果 [3]。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

Case 1 · uniform spread across 5 buckets

输入: [[-3,-1,0,1,3],-5,5,5]

期望: [0,1,2,1,1]

区间 [-5, 5] 等分为 5 个宽度为 2 的桶:[-5,-3), [-3,-1), [-1,1), [1,3), [3,5]。按 idx=floor((v-lo)/width) 计算,-3 落桶 1,-1 落桶 2,0 落桶 2,1 落桶 3,3 落桶 4。注意 3.0 算出 idx=4(恰好在右开端点),不需要裁剪。

Case 2 · all out of range — clip both sides

输入: [[100,200,-100],0,10,5]

期望: [1,0,0,0,2]

区间 [0, 10] 五桶。-100 在下界外裁到桶 0;100、200 都在上界外裁到桶 4。最终 [1,0,0,0,2]。题目规则:v < lo 进桶 0,v >= hi 进桶 n_buckets-1。

Case 3 · n_buckets=1 — everything in one bucket

输入: [[0.5,0.7,0.9],0,1,1]

期望: [3]

n_buckets=1 时整个 [lo, hi] 区间只有一个桶。任何输入(包括越界)都会被裁到桶 0。这里三个值均落入桶 0,结果 [3]。