j**l
发帖数: 2911 | 1 如果两个有序数组等长，假定都为n, 则log(n)时间找median的解法已经被讨论过很多
次了。
如果有序数组A的长度为m, 有序数组B的长度为n, 如何找log(m + n)的解法？
有人说可以padding短数组，那么padding的策略是什么？
padding是否用到了额外的空间？有没有其它方法不用额外空间，复杂度还是log(m + n
)? | S******a
发帖数: 862 | 2 http://74.53.4.74/article_t/JobHunting/31553641.html
n
【在 j**l 的大作中提到】
: 如果两个有序数组等长，假定都为n, 则log(n)时间找median的解法已经被讨论过很多
: 次了。
: 如果有序数组A的长度为m, 有序数组B的长度为n, 如何找log(m + n)的解法？
: 有人说可以padding短数组，那么padding的策略是什么？
: padding是否用到了额外的空间？有没有其它方法不用额外空间，复杂度还是log(m + n
: )?
| j**l
发帖数: 2911 | 3 多谢。这种题目会要求写代码么？感觉白板太小会写不下。而且你说的重载[]，必须是
对class才能进行的吧(比如STL给vector模板重载了[])？
【在 S******a 的大作中提到】
: http://74.53.4.74/article_t/JobHunting/31553641.html
:
: n
| j**l
发帖数: 2911 | 4 想起来，也可以是广义的重载。完全可以写一个函数
GetArrayElement(int A[], int size, int k)；
【在 j**l 的大作中提到】
: 多谢。这种题目会要求写代码么？感觉白板太小会写不下。而且你说的重载[]，必须是
: 对class才能进行的吧(比如STL给vector模板重载了[])？
| S******A
发帖数: 1002 | 5 padding: add same number of elems on left and right - what if we cannot do
it? hmm good question.
额外空间? why bother considering this? space is still in order of O(n) | j**l
发帖数: 2911 | 6 你这样的padding对么？
比如
A: 1
B: 3, 3, 3
直接求median是3
对A进行padding得到
A: 1, 1, 1
B: 3, 3, 3
求得median是2
【在 S******A 的大作中提到】
: padding: add same number of elems on left and right - what if we cannot do
: it? hmm good question.
: 额外空间? why bother considering this? space is still in order of O(n)
| k*******d
发帖数: 701 | | a*u
发帖数: 97 | 8 for padding, you should use global min (min(1,3)) and global max (max(1,3)),
instead of min/max of one array. so after padding A: 1, 1, 3, median is
still 3.
A bit tricky when n-m is odd number though.
【在 j**l 的大作中提到】
: 你这样的padding对么？
: 比如
: A: 1
: B: 3, 3, 3
: 直接求median是3
: 对A进行padding得到
: A: 1, 1, 1
: B: 3, 3, 3
: 求得median是2
| B*****t
发帖数: 335 | 9 这个本质跟两个等长数组找median道理一样，没什么区别，O(log(n+n))变成了
O(log(m+n))
多
n
【在 j**l 的大作中提到】
: 如果两个有序数组等长，假定都为n, 则log(n)时间找median的解法已经被讨论过很多
: 次了。
: 如果有序数组A的长度为m, 有序数组B的长度为n, 如何找log(m + n)的解法？
: 有人说可以padding短数组，那么padding的策略是什么？
: padding是否用到了额外的空间？有没有其它方法不用额外空间，复杂度还是log(m + n
: )?
|
|
