w********g
发帖数: 106 | 1 就出了一道千年老题，我感觉还有时间，但是对方说结束吧 -- 预感不妙。
给两个已排序数组，要求返回他们的交集和并集。
我就用两个指针分别指向两个数组，从左向右扫一遍。
我也说了hash的方法。
对方又问能不能用merge的方法，我回答能，但是不觉得复杂度更低。 |
r**h
发帖数: 1288 | 2 bless!
我觉得面试的时候一开始闲聊的时间要尽量压缩，尽早开始做题
【在 w********g 的大作中提到】
: 就出了一道千年老题，我感觉还有时间，但是对方说结束吧 -- 预感不妙。
: 给两个已排序数组，要求返回他们的交集和并集。
: 我就用两个指针分别指向两个数组，从左向右扫一遍。
: 我也说了hash的方法。
: 对方又问能不能用merge的方法，我回答能，但是不觉得复杂度更低。
|
J****3
发帖数: 427 | 3 Bless!
hash 太占空间了吧 two pointer 不就是类似merge procedure吗 怎么还问merge的方法 |
h*****a
发帖数: 1718 | 4 Binary search在某些情况下有可能降低一点复杂度，比如一个array很短，一个很长。
【在 w********g 的大作中提到】
: 就出了一道千年老题，我感觉还有时间，但是对方说结束吧 -- 预感不妙。
: 给两个已排序数组，要求返回他们的交集和并集。
: 我就用两个指针分别指向两个数组，从左向右扫一遍。
: 我也说了hash的方法。
: 对方又问能不能用merge的方法，我回答能，但是不觉得复杂度更低。
|
z****e
发帖数: 54598 | 5 merge才是最优的吧
从这题来看
尤其是已经排序了的时候
o(m+n)的复杂度
hash什么那是两个无序数组时候用的啊 |
h*****a
发帖数: 1718 | 6 No, certainly linear is not always the most efficient one. When this
algorithm is applied to the practical problem for merging reverse indexes of
search results, I guess it probably start from the shortest list and use
binary search in practice, at least for most cases when the length of the
shortest list is below some threshold.
【在 z****e 的大作中提到】
: merge才是最优的吧
: 从这题来看
: 尤其是已经排序了的时候
: o(m+n)的复杂度
: hash什么那是两个无序数组时候用的啊
|
s*******e
发帖数: 1630 | 7 同感 之前一次phone interview，还剩不到十分钟开始coding，是图论中著名的最短路
径算法，还要我剩五分钟来问她问题，一慌就有bug了
【在 r**h 的大作中提到】
: bless!
: 我觉得面试的时候一开始闲聊的时间要尽量压缩，尽早开始做题
|
r**h
发帖数: 1288 | 8 五分钟写个dijkstra？这个绝对是大牛。。。
【在 s*******e 的大作中提到】
: 同感 之前一次phone interview，还剩不到十分钟开始coding，是图论中著名的最短路
: 径算法，还要我剩五分钟来问她问题，一慌就有bug了
|
c********p
发帖数: 1969 | |
L*******e
发帖数: 114 | 10 没搞明白，难道还有更快的方法？用两个pointer就是merge了吧。哪位大牛给解释一下
。 |
|
|
l******l
发帖数: 1088 | 11 递归下？
A,m,B,n
A中比B[0]小的和比B[n-1]大的不用扫了
然后继续merge
A+k1,m-k1,B+k2,n-k2 |
c******o
发帖数: 534 | 12 除了merge还有更好方法？艹，没意思！！！
★ 发自iPhone App: ChineseWeb 7.8
【在 w********g 的大作中提到】
: 就出了一道千年老题，我感觉还有时间，但是对方说结束吧 -- 预感不妙。
: 给两个已排序数组，要求返回他们的交集和并集。
: 我就用两个指针分别指向两个数组，从左向右扫一遍。
: 我也说了hash的方法。
: 对方又问能不能用merge的方法，我回答能，但是不觉得复杂度更低。
|
h*****a
发帖数: 1718 | 13 返回交集当然有可能更好的算法，这要看array的size情况。比如，对第一个array中的
每个元素在另一个array中做binary search看这个元素是不是存在，如果存的话在加入
result集合，这样复杂度是m*log(n)。当m比较小n比较大的时候肯定是好于m+n的。
而且，这个算法本身也可以做优化，每次在第二个array中查找的时候只要从比上一个
处理的第一个array中元素大的位置开始找就可以了，所以有early termination的可能。
【在 c******o 的大作中提到】
: 除了merge还有更好方法？艹，没意思！！！
:
: ★ 发自iPhone App: ChineseWeb 7.8
|
c******o
发帖数: 534 | 14 给牛人跪了，没情绪了
能。
【在 h*****a 的大作中提到】
: 返回交集当然有可能更好的算法，这要看array的size情况。比如，对第一个array中的
: 每个元素在另一个array中做binary search看这个元素是不是存在，如果存的话在加入
: result集合，这样复杂度是m*log(n)。当m比较小n比较大的时候肯定是好于m+n的。
: 而且，这个算法本身也可以做优化，每次在第二个array中查找的时候只要从比上一个
: 处理的第一个array中元素大的位置开始找就可以了，所以有early termination的可能。
|
n*******1
发帖数: 145 | 15 我怎么感觉跟merge interval然后区分哪些是交集哪些是并 差不多 |
s***g
发帖数: 257 | 16 这个解法理论上有道理.但实际应该不是答案。
从lz的反馈讲，应该是个merge算法，稍微改进一下就可以了。
能。
【在 h*****a 的大作中提到】
: 返回交集当然有可能更好的算法，这要看array的size情况。比如，对第一个array中的
: 每个元素在另一个array中做binary search看这个元素是不是存在，如果存的话在加入
: result集合，这样复杂度是m*log(n)。当m比较小n比较大的时候肯定是好于m+n的。
: 而且，这个算法本身也可以做优化，每次在第二个array中查找的时候只要从比上一个
: 处理的第一个array中元素大的位置开始找就可以了，所以有early termination的可能。
|
c******o
发帖数: 534 | 17 怎么改进？merge是 m+n 啊
【在 s***g 的大作中提到】
: 这个解法理论上有道理.但实际应该不是答案。
: 从lz的反馈讲，应该是个merge算法，稍微改进一下就可以了。
:
: 能。
|
z****e
发帖数: 54598 | 18 楼主最开始给的是什么解法？
对方居然会问merge可以不可以？
估计一开始给的不是merge吧
是m*n的那种扫法吧？ |
