PTT
Submit
Submit
选择语言
正體中文
简体中文
PTT
Prob_Solve
[问题] 第 k 大连续子阵列和
楼主:
FRAXIS
(喔喔)
2015-02-27 22:39:11
这算是经典的最大连续子阵列和的变形吧。
给定一个长度为 n 的整数阵列,和一个正整数 k 。
找出一个在所有 C(n, 2) 个连续子阵列中,总和第 k 大的连续子阵列。
理论上是可以做到 O(n),但是这方法应该不实用。
虽然也有其他的O(n lg n),O(n lg^2 n)和O(n lg^3 n)的方法,
但是好像都不太实际 (O(n lg^3 n)的方法或许比较可行..)
我的问题是: 有没有实际上比较有效率(o(n^2))且好实作的方法呢?
这问题是在 careercup 上看到的面试问题
http://www.careercup.com/question?id=12804676
作者:
suhorng
( )
2015-02-27 23:16:00
对答案二分搜O(n log n log RANGE), 不能说是 o(n^2) 就是...
http://tioj.ck.tp.edu.tw/problems/1208
这里可以传~^^^^^ 这边不确定一个 log 还两个 log
楼主:
FRAXIS
(喔喔)
2015-02-28 02:21:00
应该是一个log 没错而且这方法也可以解决 找出长度在l~u之间的第 k 大连续和不过如果题目是找第 k 大 density 连续子阵列有没有类似的技巧可以使用呢?density 我是指 average := 总和 / 长度
作者:
DJWS
(...)
2015-02-28 07:08:00
1.算前缀和 2.穷举所有连续和/平均 3.找第k大是线性时间抱歉 我看到那是小写了...
继续阅读
Re: [问题] 主席树?
FRAXIS
Re: [问题] 主席树?
FRAXIS
Re: [问题] 主席树?
DJWS
[问题] 主席树?
FRAXIS
[问题] 一个 block 找出最少可盖覆方形个数
EdisonX
[问题] 数列问题
williamd4112
Re: [问题] 圆的资料结构
Leon
[问题] 圆的资料结构
FRAXIS
[问题] HappyStorm's Sock Sucks
williamd4112
[问题] 这样的机率数学模组可否解答的出来?
preed
Links
booklink
Contact Us: admin [ a t ] ucptt.com