chromecast 不能cast chrome浏览器？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>PDA - 掌中宝

chromecast 不能cast chrome浏览器？

chromecast 不能cast chrome浏览器？# PDA - 掌中宝

r*e2013-09-24 07:09

1 楼

We have K sorted array, A1, A2, A3,... Ak, the corresponding size for array
Ai is Ni, in total we have N numbers, N = N1 + N2 + ...+Nk. How to find the
median among N numbers in O(K (logN)^2) ?

m*k2013-09-24 07:09

2 楼

昨天和可以用，试了youku，有时会卡一下，整体还凑活，但是今天youtube可以用，
chrome不能被cast了

c*t2013-09-24 07:09

3 楼

use K min-heap, O(N*log(k))
如果用 quicksort方法，找N/2th 比较复杂，
1 取A1,A2..median元素 A1[N1/2], A2[N2/2]... 存入一个一维数组middle[K];
2 找到middle里的min Ai[Ni/2],
3. change Ai start index = Ni/2+1, 找到新的Ai median,置换掉middle[i];
4. 问题变为找剩下的第N/2 - Ni/2的元素
5. 循环2-4，直到第四步找剩下1个元素，既是middel[k]的min
应该是O(K (logN)^2)
但感觉如果把数组换成一个min-heap存 struct 会得到 O(logK （logN
)^2);

array
the

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

: We have K sorted array, A1, A2, A3,... Ak, the corresponding size for array
: Ai is Ni, in total we have N numbers, N = N1 + N2 + ...+Nk. How to find the
: median among N numbers in O(K (logN)^2) ?

c*c2013-09-24 07:09

4 楼

可以cast整个tab，youtube的话直接cast video就好了，没必要cast整个tab

l*a2013-09-24 07:09

5 楼

who has the access to acm?
these is a paper on this question.
http://apps.topcoder.com/forums/;jsessionid=8B028A73959B4AF354C

a*n2013-09-24 07:09

6 楼

多了一个cast this tab按钮。

r*e2013-09-24 07:09

7 楼

不太明白 K(logN)^2中的(logN)^2是怎么出来的。。
第2-4步，可以找middle数组中的最小和最大，将来丢掉比最小小的，比最大大的。

logN)^2);

【在 c********t 的大作中提到】

: use K min-heap, O(N*log(k))
: 如果用 quicksort方法，找N/2th 比较复杂，
: 1 取A1,A2..median元素 A1[N1/2], A2[N2/2]... 存入一个一维数组middle[K];
: 2 找到middle里的min Ai[Ni/2],
: 3. change Ai start index = Ni/2+1, 找到新的Ai median,置换掉middle[i];
: 4. 问题变为找剩下的第N/2 - Ni/2的元素
: 5. 循环2-4，直到第四步找剩下1个元素，既是middel[k]的min
: 应该是O(K (logN)^2)
: 但感觉如果把数组换成一个min-heap存 struct 会得到 O(logK （logN
: )^2);

m*k2013-09-24 07:09

8 楼

我的意思是那个按钮不管用了？每次都抱错？重新安装chrome cast extension也不行。

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

: 多了一个cast this tab按钮。

k*o2013-09-24 07:09

9 楼

我理解是KlogK * logN?
反正每次取剩下的median of medians，排序, 然后递归…
排序每次是KlogK, 每次淘汰到N/2个数字，所以总共要递归logN次…
然后因为K<=N所以是K(logN)^2?

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

: 不太明白 K(logN)^2中的(logN)^2是怎么出来的。。
: 第2-4步，可以找middle数组中的最小和最大，将来丢掉比最小小的，比最大大的。
:
: logN)^2);

r*e2013-09-24 07:09

10 楼

先赞一个深夜回复。。。
确实应该是median of median.不断丢掉当前一半规模的数据。递归log(N/K)次，因为
最后K个array中，每个array只剩下1个，一共是从总数的N减到K。
问题是，K应该是个不太大，也不太小的数，所以KlogK logN 是不是近似到KlogN?
现在脑子正糊涂。。。

【在 k**o 的大作中提到】

: 我理解是KlogK * logN?
: 反正每次取剩下的median of medians，排序, 然后递归…
: 排序每次是KlogK, 每次淘汰到N/2个数字，所以总共要递归logN次…
: 然后因为K<=N所以是K(logN)^2?

r*e2013-09-24 07:09

11 楼

谢谢，可惜不能access acm啊。
btw, I googled this question, found it is also listed as a homework question
. So, i guess 用论文的方法是否有些（我猜的啊，我还没看到论文）杀鸡用牛刀？毕
竟是STOC上的论文。。。

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

: who has the access to acm?
: these is a paper on this question.
: http://apps.topcoder.com/forums/;jsessionid=8B028A73959B4AF354C

c*t2013-09-24 07:09

12 楼

为啥要每次排序klogk？
单是找min，就是K
如果第一次排好序，以后删除头，新的值来，binary插入应该的位置，即可。其实就是
min-heap,logK

【在 k**o 的大作中提到】

s*n2013-09-24 07:09

13 楼

小想法：
1. 初始K个坐标对 [0, Ni-1]
2. 求第一个数组的media-- M1
3，去找剩下有多少比M1小的（K*lgn）
4，shrink坐标对，退化成找第k大元素
复杂度应该是K*(logN)^2 (upper bound)

l*b2013-09-24 07:09

14 楼

嗯，selection rank 的变种吧。k时间找到median of median. selection 就是对每
个数列做binary search ln a1+...+ln ak ~k ln n - k ln k ～ kln n. 一共有n个数
所以一共ln n次selection 于是得到k ln n ln n

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

: 先赞一个深夜回复。。。
: 确实应该是median of median.不断丢掉当前一半规模的数据。递归log(N/K)次，因为
: 最后K个array中，每个array只剩下1个，一共是从总数的N减到K。
: 问题是，K应该是个不太大，也不太小的数，所以KlogK logN 是不是近似到KlogN?
: 现在脑子正糊涂。。。