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? |
|