amazon的一道题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

amazon的一道题

amazon的一道题# JobHunting - 待字闺中

r*s2010-07-23 07:07

1 楼

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

J*d2010-07-23 07:07

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)的。

M*52010-07-23 07:07

3 楼

告诉了你范围的排序一般都可以在O(n)的时间之内完成的，所以你想想吧，这个不难

i*b2010-07-23 07:07

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]
}

r*s2010-07-23 07:07

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)的。

g*n2010-07-23 07:07

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]
: }

g*n2010-07-23 07:07

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 的办法.
: 我当时没想出来

V*g2010-07-23 07:07

8 楼

数量有限的话，可以counting sort。然后找出中位数。

z*n2010-07-23 07:07

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。

b*e2010-07-23 07:07

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 的大作中提到】