n≤100,可枚举所有连续子区间 [i,j]。对每个固定左端点 i,从左到右扩展右端点,并用有序插入维护当前区间的排序数组;每次扩展后按奇偶长度取中位数并累加。
偶数长度 k=2m 时,中间两数为有序数组下标 m−1 与 m,取较小者即 cur[k/2-1];奇数取 cur[k/2]。
常见假解:偶数长度取较大者或取平均;只统计奇数长度子数组。
给定互异整数数组 numbers。对每一个连续子数组,将其元素排序后取中位数并求和。中位数规定为:长度奇数取正中间;长度偶数取中间两个中的较小者。
numbers 满足 1≤numbers.length≤100,0≤numbers[i]≤105,且元素两两不同。
一个整数:所有连续子数组中位数之和。
输入:
[2, 8, 3]
输出:
21
说明:
子数组及中位数:[2]→2,[2,8]→2,[2,8,3]→3,[8]→8,[8,3]→3,[3]→3。和为 21。
输入:
[9, 1, 4, 6]
输出:
38
说明:
全部 10 个连续子数组的中位数之和为 38(可用逐段有序插入手算核对)。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.