面试题

1万 · 2013-5-24 21:57

两个无序数组A和B，长度分别是m和n，求中位数，要求时间复杂度O(m+n)，空间复杂度O(1) ？
想不出来咋实现？一点思路都没有。看看大家有啥思路没有？

只看该作者 · 2013-5-24 22:17

数组合并，长度为m+n，然后排序求出中位数，前后一次向中间靠拢进行查找即可！O(m+n)

只看该作者 · 2013-5-24 22:21

空间复杂度那个条件可以忽略，如果m>=n, index = A[(m+n-1)/2], 如果m<n, index = B[(n-m-1)/2]
主要是排序的时间复杂度达不到O(m+n)的要求

只看该作者 · 2013-5-25 08:31

这面试题难度不小

只看该作者 · 2013-5-25 08:41

火箭球迷发表于 2013-5-24 22:21
空间复杂度那个条件可以忽略，如果m>=n, index = A[(m+n-1)/2], 如果m

分析的很有道理

只看该作者 · 2013-5-26 16:04

很好的一道面试题

只看该作者 · 2013-5-26 16:21

这道面试题考察的知识还是不少的

1万 · 2013-5-28 22:58

没有哪位给个答案之类的

1万 · 2013-5-28 23:02

这个题怎看着这么的抽象的呢？没啥头绪的，虽然我的数学还是蛮好的

只看该作者 · 2013-5-28 23:18

很有技术含量的面试题

只看该作者 · 2013-5-30 22:35

这个是什么企业的面试题

只看该作者 · 2013-5-31 21:54

这面试题难度不小，估计是外企的面试题吧