s*i
发帖数: 5025 | 1 Given three arrays A,B,C containing unsorted numbers. Find three numbers a,
b, c from each of array A, B, C such that |a-b|, |b-c| and |c-a| are minimum
Please provide as efficient code as you can. | l*****a
发帖数: 14598 | 2 sort separately,
then merge multiple sorted list?
,
minimum
【在 s*i 的大作中提到】
: Given three arrays A,B,C containing unsorted numbers. Find three numbers a,
: b, c from each of array A, B, C such that |a-b|, |b-c| and |c-a| are minimum
: Please provide as efficient code as you can.
| A*****i
发帖数: 3587 | | A*****i
发帖数: 3587 | 4 错了应该是初中奥数题，多项式展开还是怎么来着，以前一定做过 | f*******w
发帖数: 1243 | 5 什么叫|a-b|, |b-c|, |c-a|最小？
三个的和最小？ | s*i
发帖数: 5025 | 6 他们之间最大的，最小。
彼此间的距离。
【2，4，8】
【1，9，3】
【-4，7，6】
8，9，7是解 | r****7
发帖数: 2282 | 7 any better solution so far?
【在 l*****a 的大作中提到】
: sort separately,
: then merge multiple sorted list?
:
: ,
: minimum
| h*******e
发帖数: 1377 | 8 O(n logn)?
刚看了阿里题目 2013ali也有这道题。 | r*****3
发帖数: 27 | 9 O(n1+n2+n3) n1,n2,n3 是三个数组的长度
|a-b|+|b-c|+|c-a| 其实就是求 2*(最大数-最小数) (eg. 如果a>b>c, |a-b|+|b-c|+|
c-a| = 2(a-c) )
三个指针i, j, k
从头开始扫, 总是移动最小的那个指针 更新当前最小的 2*(最大数-最小数) 即可
证明正确性:
在扫的过程中, 对于三个数组中的任意一个数, 分三种情况讨论 (下面假设取出的三个
数 a>b>c)
1. 如果他作为b, 那么永远不影响最后结果
2. 如果他作为a, 在他作为a的时候, 由于一直在移动另两个指针并接近a, 肯定能扫到
那个对于a而言最大的c
3. 如果他作为c, 假设 a或者b不是自己数组中比c大的最小值, 那么肯定有在c数组还
没扫到c的时候有移动a,b数组指针的情况, 但这和假设矛盾
证明写的有点乱 求大神更好更清楚的证明
EDIT: 看错了, 应该先sort的 = = | n*****n
发帖数: 5277 | 10 语文水平需要提高
【在 s*i 的大作中提到】
: 他们之间最大的，最小。
: 彼此间的距离。
: 【2，4，8】
: 【1，9，3】
: 【-4，7，6】
: 8，9，7是解
| | | t*******e
发帖数: 274 | 11 这题有比较简洁明了的解法么? careercup上看到20多个回帖，看上去每个都不一样 | s*i
发帖数: 5025 | 12 我看 robot13的解法挺好的。
[发表自未名空间手机版 - m.mitbbs.com]
【在 t*******e 的大作中提到】
: 这题有比较简洁明了的解法么? careercup上看到20多个回帖，看上去每个都不一样
| t*******e
发帖数: 274 | 13 有具体的代码实现么？感觉先决条件a>b>c不一定能满足啊
【在 s*i 的大作中提到】
: 我看 robot13的解法挺好的。
:
: [发表自未名空间手机版 - m.mitbbs.com]
| z******t
发帖数: 59 | 14 写了一下代码，放在
http://ideone.com/M3ZaKt
测了几个test case，都过了
【在 t*******e 的大作中提到】
: 有具体的代码实现么？感觉先决条件a>b>c不一定能满足啊
| m******a
发帖数: 84 | 15 可以直接就用set来做，A和B分别放到seta, setb里面，然后遍历C，对C[i]找seta.
lower_bound(C[i]), seta.lower_bound(C[i])-1, setb.lower_bound(C[i]), setb.
lower_bound(C[i])-1，然后seta, setb和C[I]组合来计算，也是nlogn的 | l*********b
发帖数: 65 | 16 赶紧robot13的解法挺好的 排序nlogN 然后搜索只要N 虽然总体是nlogN 但是思路比较
清楚而且好说好实现 | m*****k
发帖数: 731 | 17 这题本质上貌似是Finding the Minimum Window in S which Contains All Elements
from T ?
,
minimum
【在 s*i 的大作中提到】
: Given three arrays A,B,C containing unsorted numbers. Find three numbers a,
: b, c from each of array A, B, C such that |a-b|, |b-c| and |c-a| are minimum
: Please provide as efficient code as you can.
|
|
