c*********n
发帖数: 1057 | 1 两个sorted array A B
A足够大，把B放到A里，
经典解法是从后往前iterate
但面试官不满意，问有什么改进
我说每次iterate的时候看当前的两个element是不是A[0],或者B[0]，是的话直接copy
剩下的
但面试官还是不满意，想问问有什么其他improvement么？或者更好的解法？ |
c****s
发帖数: 241 | 2 可以用binary search来加快找的速度。不知道有没有更好的办法？
copy
【在 c*********n 的大作中提到】
: 两个sorted array A B
: A足够大，把B放到A里，
: 经典解法是从后往前iterate
: 但面试官不满意，问有什么改进
: 我说每次iterate的时候看当前的两个element是不是A[0],或者B[0]，是的话直接copy
: 剩下的
: 但面试官还是不满意，想问问有什么其他improvement么？或者更好的解法？
|
b****r
发帖数: 1272 | 3 有点意思，不用找A[0] B[0]位置吧，那个循环在任一个array到头时就跳出了
难道有比O(min(m,n))更好的？ |
c*********n
发帖数: 1057 | 4
~~~~~~~~~~~~~~~~~~~~~~~对啊我就这个意思
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~这个可能不对吧？
【在 b****r 的大作中提到】
: 有点意思，不用找A[0] B[0]位置吧，那个循环在任一个array到头时就跳出了
: 难道有比O(min(m,n))更好的？
|
r****o
发帖数: 1950 | 5 呼唤小尾羊。
【在 b****r 的大作中提到】
: 有点意思，不用找A[0] B[0]位置吧，那个循环在任一个array到头时就跳出了
: 难道有比O(min(m,n))更好的？
|
r****o
发帖数: 1950 | 6 为什么可能不对?
【在 c*********n 的大作中提到】
:
: ~~~~~~~~~~~~~~~~~~~~~~~对啊我就这个意思
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~这个可能不对吧？
|
l***i
发帖数: 1309 | |
c*********n
发帖数: 1057 | 8 我面试的时候想到了binary search，但是我自己都没想清楚，怎么个binary search法
呢？
【在 c****s 的大作中提到】
: 可以用binary search来加快找的速度。不知道有没有更好的办法？
:
: copy
|
c*********n
发帖数: 1057 | 9 对的，我一下没想清楚
【在 r****o 的大作中提到】
: 为什么可能不对?
|
h*********e
发帖数: 56 | 10 A size N, B size M.
你的算法是insertion sort, O(NM).
可以用先把 A 变成 heap，insert B，再heap sort。O((N+M)ln(N+M)).
或者直接append B, then heap sort. |
d**a
发帖数: 84 | 11 就是从后往前 merge吧，这还能咋提高？min(m,n),怎么着也得复制过去吧。如果想减
少比较次数，是可以搞个binary search，可那是主要代价吗？
copy
【在 c*********n 的大作中提到】
: 两个sorted array A B
: A足够大，把B放到A里，
: 经典解法是从后往前iterate
: 但面试官不满意，问有什么改进
: 我说每次iterate的时候看当前的两个element是不是A[0],或者B[0]，是的话直接copy
: 剩下的
: 但面试官还是不满意，想问问有什么其他improvement么？或者更好的解法？
|
c*********n
发帖数: 1057 | 12 A 和 B 都已经sort好了的
【在 h*********e 的大作中提到】
: A size N, B size M.
: 你的算法是insertion sort, O(NM).
: 可以用先把 A 变成 heap，insert B，再heap sort。O((N+M)ln(N+M)).
: 或者直接append B, then heap sort.
|
h*********e
发帖数: 56 | 13 这题是要找个中数，还是全排序阿？怎么也不说明白？ |
