各位在usmattress上买床垫的# Living
g*s
1 楼
let's assume they all have n elements.
for k = 2, it's classical. but how about the general "k"?
for k = 2, it's classical. but how about the general "k"?
t*r
2 楼
只知道NIW要交,EB1需要吗?谢了
h*s
3 楼
觉得和local店里的质量一样吗，在各种参数都一致的情况下。想必大家都是对了参数
的。
的。
l*a
4 楼
I can only handle it with
n*K/2*lgk
【在 g*********s 的大作中提到】
: let's assume they all have n elements.
: for k = 2, it's classical. but how about the general "k"?
n*K/2*lgk
【在 g*********s 的大作中提到】
: let's assume they all have n elements.
: for k = 2, it's classical. but how about the general "k"?
R*n
5 楼
不需要
s*d
6 楼
如果牌子参数一样的，就是一样的东西。
g*s
7 楼
Even if it is not sorted, the finding median of all (k*n) item only needs
O(k*n)
【在 l*****a 的大作中提到】
: I can only handle it with
: n*K/2*lgk
O(k*n)
【在 l*****a 的大作中提到】
: I can only handle it with
: n*K/2*lgk
W*R
8 楼
no
h*s
9 楼
sure?
【在 s********d 的大作中提到】
: 如果牌子参数一样的，就是一样的东西。
【在 s********d 的大作中提到】
: 如果牌子参数一样的，就是一样的东西。
c*6
10 楼
agree
把k个array当作一个用partition algorithm
cheers！！
【在 g***s 的大作中提到】
: Even if it is not sorted, the finding median of all (k*n) item only needs
: O(k*n)
把k个array当作一个用partition algorithm
cheers！！
【在 g***s 的大作中提到】
: Even if it is not sorted, the finding median of all (k*n) item only needs
: O(k*n)
f*w
11 楼
怎么当作一个array?
h*d
12 楼
什么意思，再讲下？
【在 c**********6 的大作中提到】
: agree
: 把k个array当作一个用partition algorithm
: cheers！！
【在 c**********6 的大作中提到】
: agree
: 把k个array当作一个用partition algorithm
: cheers！！
l*a
13 楼
could u share your code
thanks
【在 g***s 的大作中提到】
: Even if it is not sorted, the finding median of all (k*n) item only needs
: O(k*n)
thanks
【在 g***s 的大作中提到】
: Even if it is not sorted, the finding median of all (k*n) item only needs
: O(k*n)
g*s
14 楼
1. put all number into one array, size = k*n O(k*n)
2. find the median of the array O(k*n)
I think LZ is asking for a better solution since the above method doesn't
care if it is sorted or not in the k arrays.
【 在 lolhaha (haha) 的大作中提到: 】
2. find the median of the array O(k*n)
I think LZ is asking for a better solution since the above method doesn't
care if it is sorted or not in the k arrays.
【 在 lolhaha (haha) 的大作中提到: 】
g*s
15 楼
yes, for k=2, O(lgN) is surely much better.
doesn't
【在 g***s 的大作中提到】
: 1. put all number into one array, size = k*n O(k*n)
: 2. find the median of the array O(k*n)
: I think LZ is asking for a better solution since the above method doesn't
: care if it is sorted or not in the k arrays.
: 【 在 lolhaha (haha) 的大作中提到: 】
doesn't
【在 g***s 的大作中提到】
: 1. put all number into one array, size = k*n O(k*n)
: 2. find the median of the array O(k*n)
: I think LZ is asking for a better solution since the above method doesn't
: care if it is sorted or not in the k arrays.
: 【 在 lolhaha (haha) 的大作中提到: 】
n*p
16 楼
what if the memory can only hold two arrays rather than all the arrays.
【在 g***s 的大作中提到】
: 1. put all number into one array, size = k*n O(k*n)
: 2. find the median of the array O(k*n)
: I think LZ is asking for a better solution since the above method doesn't
: care if it is sorted or not in the k arrays.
: 【 在 lolhaha (haha) 的大作中提到: 】
【在 g***s 的大作中提到】
: 1. put all number into one array, size = k*n O(k*n)
: 2. find the median of the array O(k*n)
: I think LZ is asking for a better solution since the above method doesn't
: care if it is sorted or not in the k arrays.
: 【 在 lolhaha (haha) 的大作中提到: 】
j*x
17 楼
对每个数组，二分其元素，然后在其他数组中二分查找其左侧（小于）和右侧（大于）
的元素个数
k*O(log^2n)
如果不能同时放入内存，重复上面的过程，每次从载入一个数组即可
的元素个数
k*O(log^2n)
如果不能同时放入内存，重复上面的过程，每次从载入一个数组即可
g*s
18 楼
Could not understand:
"然后在其他数组中二分查找其左侧（小于）和右侧（大于）"
what's the '其'?
【在 j********x 的大作中提到】
: 对每个数组，二分其元素，然后在其他数组中二分查找其左侧（小于）和右侧（大于）
: 的元素个数
: k*O(log^2n)
: 如果不能同时放入内存，重复上面的过程，每次从载入一个数组即可
"然后在其他数组中二分查找其左侧（小于）和右侧（大于）"
what's the '其'?
【在 j********x 的大作中提到】
: 对每个数组，二分其元素，然后在其他数组中二分查找其左侧（小于）和右侧（大于）
: 的元素个数
: k*O(log^2n)
: 如果不能同时放入内存，重复上面的过程，每次从载入一个数组即可
a*7
19 楼
CLRS -> Chapter 9: Medians and Order Statistics -> Selection in worst-case
linear time
linear time
g*s
20 楼
here we are discussing a solution better than O(kn) 【 在 anson627 (anson)
的大作中提到: 】
case
的大作中提到: 】
case
a*7
21 楼
the book already assumed each sorting in O(1) time, when the sub-array is
small enough. I don't think we can do better in worst case. On average case,
maybe.
small enough. I don't think we can do better in worst case. On average case,
maybe.
相关阅读
附近孩子破坏了我家摄像头，但都被拍下，是先找家长还是直接叫警察50-60cm 直径的树干，DIY用啥工具呀？版上有人用home warranty嘛？还是全部DIY朋友打电话说，孩子要留学，要到我家来住，怎么拒绝呢自住房 Refinance， Daily Interest Charges 问题我要把病号公婆送回家，不对？草都黄了Lowes的各种coupon换空调求教imore版主如何查房屋保险以前的claim？最近装修院子被老墨坑了impact driver和hammer driver分别对应中文的什么姐姐妈妈都来了，好高兴哦。我却不想带她们去星巴客engineering 地板被水泡了一天感觉我被structure engineer骗了收到水公司的信要做backflow provention device testHow bad is Radon 5.1 without remediation? (转载)请问版上有做Iowa贷款的broker么？马桶漏水，楼下发霉， 房客提前搬走，我负责哪些责任？能否在已有的窗户上再加一层隔音玻璃？