桶排序构建盈亏直方图
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 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
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]。