G***G
发帖数: 16778 | 1 一个向量，100000个数值。在数轴上按顺序排开。总共100000格子。
一个数轴的滑块宽度是1000。滑块从左到右顺序沿数轴滑动，每次滑动一个数值格子
如何求出其每次滑过的里面包含的1000个数值的最小值。
要求：可以避免每次都重新计算这1000个数值的最小值吗？
因为我们已经知道前1000个数值的最小值，也知道当前数值的大小。
假如将当前的数字都乘以100，也就是10000000个数值，窗口尺寸为100000
你的算法会不会占用大量cpu时间？ |
g********6
发帖数: 86 | 2 先判断滑出的值是否等于最小值，如果相等，重新计算当前窗口最小值；如果不相等，
比较最小值和滑入数值大小，取较小值重新赋值当前最小值 |
v*******e
发帖数: 11604 | 3 看楼主的要求，就是把10000个数排序，第一次取最小的一个，第二次去次小的一个，
第三次取第三小的一个，就行了。没看出来有任何算法的必要。 |
w********m
发帖数: 1137 | 4 搜索 sliding window maximum
★ 发自iPhone App: ChineseWeb 8.7
【在 G***G 的大作中提到】
: 一个向量，100000个数值。在数轴上按顺序排开。总共100000格子。
: 一个数轴的滑块宽度是1000。滑块从左到右顺序沿数轴滑动，每次滑动一个数值格子
: 如何求出其每次滑过的里面包含的1000个数值的最小值。
: 要求：可以避免每次都重新计算这1000个数值的最小值吗？
: 因为我们已经知道前1000个数值的最小值，也知道当前数值的大小。
: 假如将当前的数字都乘以100，也就是10000000个数值，窗口尺寸为100000
: 你的算法会不会占用大量cpu时间？
|
M*P
发帖数: 6456 | 5 怎么搞都是线性的啊。
★ 发自iPhone App: ChineseWeb 7.8
【在 G***G 的大作中提到】
: 一个向量，100000个数值。在数轴上按顺序排开。总共100000格子。
: 一个数轴的滑块宽度是1000。滑块从左到右顺序沿数轴滑动，每次滑动一个数值格子
: 如何求出其每次滑过的里面包含的1000个数值的最小值。
: 要求：可以避免每次都重新计算这1000个数值的最小值吗？
: 因为我们已经知道前1000个数值的最小值，也知道当前数值的大小。
: 假如将当前的数字都乘以100，也就是10000000个数值，窗口尺寸为100000
: 你的算法会不会占用大量cpu时间？
|
w****i
发帖数: 964 | 6 use a heap for the 1000 number |
