avatar
amazon的一道题# JobHunting - 待字闺中
r*s
1
电话里面问的:
有n个数, value range from 0-255, 找出 median value的那个数
我说先quick sort, 然后 第 n/2 那个就是了. 他说有更efficient 的办法.
我当时没想出来
avatar
J*d
2
首先,楼主的解法我认为是不正确的。
如果这n个数quick sort的结果是1,1,1,1,1,...1,2,3 (除了最后两个数全是1),
那么答案应该是2而不是1.
如果我们遍历一遍看n个数里面有没有0,1,2,...255。(用上面的例子,结果是1,2,3)
然后在有的值里面把median value求出来。算法应该是O(n)的。
avatar
M*5
3
告诉了你范围的排序一般都可以在O(n)的时间之内完成的,所以你想想吧,这个不难
avatar
i*b
4
难道不能logn么。
就用A[0]作为划分元素。 假设A[0]最后位置是i
while(true) {
if i==n/2, 它就是median, return;
if i < n/2, 拿A[i + 1]作为划分元素划分A[i + 1] 到 A[n - 1]
if i > n/2 拿A[i - 1] 作为划分元素划分A[0] 到 A[i - 1]
}
avatar
r*s
5
我题目说的可能不是很清楚, median value 指的是:
如果n个数是 1, 1, 1, 2, 3, 那么median value 就是 1,
就是sort完后最中间位置的那个数

【在 J******d 的大作中提到】
: 首先,楼主的解法我认为是不正确的。
: 如果这n个数quick sort的结果是1,1,1,1,1,...1,2,3 (除了最后两个数全是1),
: 那么答案应该是2而不是1.
: 如果我们遍历一遍看n个数里面有没有0,1,2,...255。(用上面的例子,结果是1,2,3)
: 然后在有的值里面把median value求出来。算法应该是O(n)的。

avatar
g*n
6
“假设A[0]最后位置是i” -- 用log(n)时间你怎么知道i?

【在 i**********b 的大作中提到】
: 难道不能logn么。
: 就用A[0]作为划分元素。 假设A[0]最后位置是i
: while(true) {
: if i==n/2, 它就是median, return;
: if i < n/2, 拿A[i + 1]作为划分元素划分A[i + 1] 到 A[n - 1]
: if i > n/2 拿A[i - 1] 作为划分元素划分A[0] 到 A[i - 1]
: }

avatar
g*n
7
开个256大小的hash是个解决办法。O(n)过一遍,map[A[i]]++。然后算SUM(map[j])(j
从0开始,
到255),直到第一个j使SUM >= n/2,这个j就是median。

【在 r*********s 的大作中提到】
: 电话里面问的:
: 有n个数, value range from 0-255, 找出 median value的那个数
: 我说先quick sort, 然后 第 n/2 那个就是了. 他说有更efficient 的办法.
: 我当时没想出来

avatar
V*g
8
数量有限的话,可以counting sort。然后找出中位数。
avatar
z*n
9
对,就是这个思路,因为知道range,用数组代替hash也行

j

【在 g****n 的大作中提到】
: 开个256大小的hash是个解决办法。O(n)过一遍,map[A[i]]++。然后算SUM(map[j])(j
: 从0开始,
: 到255),直到第一个j使SUM >= n/2,这个j就是median。

avatar
b*e
10
if no extra space to use, we can use selection alrogithm
1. choose (0,255)/2 as pivort
2. after that, choose (b,255)/2 or (0,b)/2 as pivot
3.....
if with extra space, we can use hash

【在 r*********s 的大作中提到】
: 电话里面问的:
: 有n个数, value range from 0-255, 找出 median value的那个数
: 我说先quick sort, 然后 第 n/2 那个就是了. 他说有更efficient 的办法.
: 我当时没想出来

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。