r*********s
发帖数: 2157 | 1 电话里面问的:
有n个数, value range from 0-255, 找出 median value的那个数
我说先quick sort, 然后 第 n/2 那个就是了. 他说有更efficient 的办法.
我当时没想出来 | J******d
发帖数: 506 | 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********5
发帖数: 715 | 3 告诉了你范围的排序一般都可以在O(n)的时间之内完成的，所以你想想吧，这个不难 | i**********b
发帖数: 77 | 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*********s
发帖数: 2157 | 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****n
发帖数: 431 | 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****n
发帖数: 431 | 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*******g
发帖数: 678 | 8 数量有限的话，可以counting sort。然后找出中位数。 | z****n
发帖数: 1379 | 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********e
发帖数: 693 | 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 的办法.
: 我当时没想出来
|
|
