推荐简单小巧的缝纫机？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Living

推荐简单小巧的缝纫机？

推荐简单小巧的缝纫机？# Living

m*r2011-11-09 08:11

1 楼

This is an interview question. The interview has been done.
Given a sequence of data (it may have duplicates), a fixed-sized moving
window, move the window at each iteration from the start of the data
sequence, such that
(1) the oldest data element is removed from the window and a new data
element is pushed into the window
(2) find the median of the data inside the window at each moving.
My idea:
Use 2 heaps to hold median. In side the window, sort the data in the window
in the first iteration, the min heap holds the larger part and the max heap
holds the smaller part. If the window has odd number of data, the max heap
returns the median otherwise the arithmetic mean of the top elements of the
two heaps is the median.
When a new data is pushed in to the window, remove the oldest data from one
of the heap and compare the new data with the top of max and min heap so
that to decide which heap the data to be put. Then, find the median just
like in the first iteration.
But, how to find a data element in a heap is a problem. Heap is a binary
tree not a binary search tree.
Any help is really appreciated.
Thanks

m*n2011-11-09 08:11

2 楼

大概什么牌子，多少价格，在哪里买？
俺要缝的东西面积不大，但是还是要精确才好
还有这东西可不可以买二手的？
谢谢。

h*l2011-11-09 08:11

3 楼

除了第一次，以后应该都是 O（1）
第一次sort一下window里面n个数记下median
然后删一个数，跟median比较，你就知道左边还是右边，或者median被删，也是一样的
新加一个数，也知道median左边右边
如果在median两边， median不变，
不然就是median旁边一个是新的median，左边右边判断一下
window是偶数情况应该类似的

window
heap

【在 m****r 的大作中提到】

: This is an interview question. The interview has been done.
: Given a sequence of data (it may have duplicates), a fixed-sized moving
: window, move the window at each iteration from the start of the data
: sequence, such that
: (1) the oldest data element is removed from the window and a new data
: element is pushed into the window
: (2) find the median of the data inside the window at each moving.
: My idea:
: Use 2 heaps to hold median. In side the window, sort the data in the window
: in the first iteration, the min heap holds the larger part and the max heap

F*e2011-11-09 08:11

4 楼

这个咋样？
http://amzn.to/tP8Fdk

l*i2011-11-09 08:11

5 楼

Use a balanced BST

m*n2011-11-09 08:11

6 楼

这个是不是太小了？还是用电池的。。。
咱们还是预算100左右。。。

【在 F**********e 的大作中提到】

: 这个咋样？
: http://amzn.to/tP8Fdk

s*n2011-11-09 08:11

7 楼

新的数插哪里你没说

【在 h**********l 的大作中提到】

: 除了第一次，以后应该都是 O（1）
: 第一次sort一下window里面n个数记下median
: 然后删一个数，跟median比较，你就知道左边还是右边，或者median被删，也是一样的
: 新加一个数，也知道median左边右边
: 如果在median两边， median不变，
: 不然就是median旁边一个是新的median，左边右边判断一下
: window是偶数情况应该类似的
:
: window
: heap

F*e2011-11-09 08:11

8 楼

呵呵，那就瞧瞧这个吧，150打折到85 Good luck
http://amzn.to/vONdnm

【在 m*****n 的大作中提到】

: 这个是不是太小了？还是用电池的。。。
: 咱们还是预算100左右。。。

s*n2011-11-09 08:11

9 楼

window分成1个maxheap紧接1个minheap，保持2个heap的大小最多差1，maxheap的最大
值小于等于minheap的最小值。复杂度每插入一个数是log(L)，L是window的大小。

m*n2011-11-09 08:11

10 楼

谢谢！！

【在 F**********e 的大作中提到】

: 呵呵，那就瞧瞧这个吧，150打折到85 Good luck
: http://amzn.to/vONdnm

h*l2011-11-09 08:11

11 楼

应该继续放在sorted的 window里面， window 大小的log复杂度

【在 s******n 的大作中提到】

: 新的数插哪里你没说

c*92011-11-09 08:11

12 楼

如果每次都是删除oldest element的话需要一个额外的array来存window大小的按照old
顺序排序的吧，其他同happy的解法

m*r2011-11-09 08:11

13 楼

thanks,
How to find the oldest element in the heaps ?

【在 s******n 的大作中提到】

: window分成1个maxheap紧接1个minheap，保持2个heap的大小最多差1，maxheap的最大
: 值小于等于minheap的最小值。复杂度每插入一个数是log(L)，L是window的大小。

s*n2011-11-09 08:11

14 楼

没看到这个要求。。。如果有这个要求就复杂了，得搞double-link-list，heap调整的
时候也要调整link-list

【在 m****r 的大作中提到】

: thanks,
: How to find the oldest element in the heaps ?

m*i2011-11-09 08:11

15 楼

要往sort windows里插入数字，看你的sorted window是什么结构了。假设window
size是L。如果 window是array,那么找到要删除的数字是lg(L)，找到要插入的位子lg(
L), 移动2个数字之间的数字要L. 也就是每次都要O(L)的时间复杂度。如果我windows
是linklist也是O(L), 所以要想log(L)就要用BST或skip list. 不知道你说的O（1）如
何得到的。

【在 h**********l 的大作中提到】

: 应该继续放在sorted的 window里面， window 大小的log复杂度

w*o2011-11-09 08:11

16 楼

好难呀

【在 m****r 的大作中提到】

m*r2011-11-09 08:11

17 楼

So, in your way, the total complexity is
O(n * m), where n is number of data, m is the window size.
Space complexity: O(m), you need to copy the data in the window to an array.
Right ?

lg(
windows

【在 m****i 的大作中提到】

: 要往sort windows里插入数字，看你的sorted window是什么结构了。假设window
: size是L。如果 window是array,那么找到要删除的数字是lg(L)，找到要插入的位子lg(
: L), 移动2个数字之间的数字要L. 也就是每次都要O(L)的时间复杂度。如果我windows
: 是linklist也是O(L), 所以要想log(L)就要用BST或skip list. 不知道你说的O（1）如
: 何得到的。

c*e2011-11-09 08:11

18 楼

My solution: Suppose the window width is L.
Use two heaps, one min-heap and one max-heap, and an array Node* arr[L],
which are pointers to the nodes.
Each node of the heap is a structure. It not only includes the data, a left
pointer, and a right pointer, but also an integer. The integer is the
location of the node in the array.
When we delete an value from the window, we know its location i (0 <= i < L)
. By arr[i], we find the node in either heap, and we delete it. When we
delete the node, some other nodes will also be "moved" in the heap, so there
pointers in arr[] will also be updated. The operation is O(log(L)).
For the new value, we make a new node, and insert to either heap. The
operation is also O(log(L)).
So the total complexity is O(n*log(L)).