b*******8
发帖数: 33 | 1 这是道老题。通常的方法是用两个pointers 从头到尾过两个arrays。复杂度是O(n).
但是如果一个array要比另一个大很多，则我们要Binary Search.复杂度是O(nlgm)。
扩展题是，在下面的情况下，how to optimize the search process (we may need to
switch between O(n) and O(nlgm) methods),
case 1:
v1: 1, 100, ......, 200,300,......,400
v2: 1,......, 100, 200, ......,300,400
case 2:
v1: 1,3,4,7,......,1M+1
v2: 2,4,6,8,...... 1M
case 3:
v1: 1,300, 5000, 70000, ......,1M+1
v2: 2,400, 6000, 80000, ......, 1M
求告人指点。 | g*****k
发帖数: 623 | 2 就像你说的，这个就是由size决定的。
to
【在 b*******8 的大作中提到】
: 这是道老题。通常的方法是用两个pointers 从头到尾过两个arrays。复杂度是O(n).
: 但是如果一个array要比另一个大很多，则我们要Binary Search.复杂度是O(nlgm)。
: 扩展题是，在下面的情况下，how to optimize the search process (we may need to
: switch between O(n) and O(nlgm) methods),
: case 1:
: v1: 1, 100, ......, 200,300,......,400
: v2: 1,......, 100, 200, ......,300,400
: case 2:
: v1: 1,3,4,7,......,1M+1
: v2: 2,4,6,8,...... 1M
| b*******8
发帖数: 33 | 3 但是在给出的三个cases里面，他们的size都差不多。所以一般用O(n)的方法。扩展题
的意思能不能通过某种优化，有比O(n)更好的方法。 | b*******8
发帖数: 33 | 4 有高人指点怎么优化1楼的三个cases吗？特别是case 2 and case 3? |
|
