s*******e
发帖数: 4188 | 1 saw this on careercup:
3 sorted arrays, A, B, C, find indexes i, j, k, so that max(a-b, b-c, c-a)
is minimized. (a = A[i], b = B[j], c = C[k])
Another version is to minimize max(|a-b|, |b-c|, |c-a|). | d*******d
发帖数: 2050 | 2 我直接反映是对每个A的元素,在b里面bsearch,search到一个或两个,再在c里search,
再笨办法比,留最好的.
mlogn,m is the shortest of abc.
【在 s*******e 的大作中提到】
: saw this on careercup:
: 3 sorted arrays, A, B, C, find indexes i, j, k, so that max(a-b, b-c, c-a)
: is minimized. (a = A[i], b = B[j], c = C[k])
: Another version is to minimize max(|a-b|, |b-c|, |c-a|).
| d*******d
发帖数: 2050 | 3 我的第二反应是,有没有可能用类似merge array的算法.
【在 s*******e 的大作中提到】
: saw this on careercup:
: 3 sorted arrays, A, B, C, find indexes i, j, k, so that max(a-b, b-c, c-a)
: is minimized. (a = A[i], b = B[j], c = C[k])
: Another version is to minimize max(|a-b|, |b-c|, |c-a|).
| d*******d
发帖数: 2050 | 4 yeah,就是这个,merge 3 array那样走一边,update current correspond head of ABC,
after each update, recalculate the target value, keep the best one.
O(n);
code写好看了不容易.
【在 d*******d 的大作中提到】
: 我的第二反应是,有没有可能用类似merge array的算法.
| C***U
发帖数: 2406 | 5 O(n)能实现
三个array集中到一个array
【在 s*******e 的大作中提到】
: saw this on careercup:
: 3 sorted arrays, A, B, C, find indexes i, j, k, so that max(a-b, b-c, c-a)
: is minimized. (a = A[i], b = B[j], c = C[k])
: Another version is to minimize max(|a-b|, |b-c|, |c-a|).
| S******1
发帖数: 269 | 6 思路和那个找出包括所有keywords最短的subString一样吧。 | a********m
发帖数: 15480 | 7 纯merge不行吧。还要保证abc在三个数组中。 |
|
