作者FRAXIS (喔喔)
看板Prob_Solve
标题[问题] 第 k 大连续子阵列和
时间Fri Feb 27 22:39:11 2015
这算是经典的最大连续子阵列和的变形吧。
给定一个长度为 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
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 129.170.195.149
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1425047953.A.AAD.html
※ 编辑: FRAXIS (129.170.195.149), 02/27/2015 22:40:17
1F：推 suhorng: 对答案二分搜 02/27 23:16
2F：→ suhorng: O(n log n log RANGE), 不能说是 o(n^2) 就是... 02/27 23:18
4F：→ suhorng: ^^^^^ 这边不确定一个 log 还两个 log 02/28 02:07
5F：→ FRAXIS: 应该是一个log 没错 02/28 02:21
6F：→ FRAXIS: 而且这方法也可以解决 找出长度在l~u之间的第 k 大连续和 02/28 02:22
7F：→ FRAXIS: 不过如果题目是找第 k 大 density 连续子阵列 02/28 02:23
8F：→ FRAXIS: 有没有类似的技巧可以使用呢？ 02/28 02:23
9F：→ FRAXIS: density 我是指 average := 总和 / 长度 02/28 02:25
10F：推 DJWS: 1.算前缀和 2.穷举所有连续和/平均 3.找第k大是线性时间 02/28 07:08
11F：→ DJWS: 抱歉 我看到那是小写了... 02/28 07:09