定尺寸求10000个数值的最小值 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Biology - 生物学

定尺寸求10000个数值的最小值

定尺寸求10000个数值的最小值# Biology - 生物学

G*G2014-11-27 08:11

1 楼

一个向量，100000个数值。在数轴上按顺序排开。总共100000格子。
一个数轴的滑块宽度是1000。滑块从左到右顺序沿数轴滑动，每次滑动一个数值格子
如何求出其每次滑过的里面包含的1000个数值的最小值。
要求：可以避免每次都重新计算这1000个数值的最小值吗？
因为我们已经知道前1000个数值的最小值，也知道当前数值的大小。
假如将当前的数字都乘以100，也就是10000000个数值，窗口尺寸为100000
你的算法会不会占用大量cpu时间？

g*62014-11-27 08:11

2 楼

先判断滑出的值是否等于最小值，如果相等，重新计算当前窗口最小值；如果不相等，
比较最小值和滑入数值大小，取较小值重新赋值当前最小值

v*e2014-11-27 08:11

3 楼

看楼主的要求，就是把10000个数排序，第一次取最小的一个，第二次去次小的一个，
第三次取第三小的一个，就行了。没看出来有任何算法的必要。

w*m2014-11-27 08:11

4 楼

搜索 sliding window maximum

★ 发自iPhone App: ChineseWeb 8.7

【在 G***G 的大作中提到】

: 一个向量，100000个数值。在数轴上按顺序排开。总共100000格子。
: 一个数轴的滑块宽度是1000。滑块从左到右顺序沿数轴滑动，每次滑动一个数值格子
: 如何求出其每次滑过的里面包含的1000个数值的最小值。
: 要求：可以避免每次都重新计算这1000个数值的最小值吗？
: 因为我们已经知道前1000个数值的最小值，也知道当前数值的大小。
: 假如将当前的数字都乘以100，也就是10000000个数值，窗口尺寸为100000
: 你的算法会不会占用大量cpu时间？