B*******1
发帖数: 2454 | 1 Given n arrays, find n number such that sum of their differences is minimum.
For e.g. if there are three arrays
A = {4, 10, 15, 20}
B = {1, 13, 29}
C = {5, 14, 28}
find three numbers a, b, c such that |a-b| + |b-c| + |c-a| is minimum. Here
the answer is a = 15, b = 13, and c = 14 | f*******t
发帖数: 7549 | 2 divide&conquer?
我只是猜测，想不出具体算法 | g*****i
发帖数: 2162 | 3 O(n)吧,|a-b| + |b-c| + |c-a| = (Max(abc)-Min(abc))*2,然后每个array排序后一个
pointer,最小的那组移动. | B*******1
发帖数: 2454 | 4 可以具体说说嘛？
譬如题目里面说的那个例子。
thanks | d***n
发帖数: 65 | 5 |a-b| + |b-c| + |c-a| = (Max(abc)-Min(abc))*2对n=3成立
用这个思路，一般情况还是需要O(n)的时间来计算差和。
先对每个array排序时间O(klogk), k是array平均长度。
然后根据每个array最小的数对所有array排序时间O(nlogn)。
scan的时候要维持所有array按当前数的大小排序，每scan一个数需要logn时间调整排序（binary search or heap），计算新的差和O(n), scan完所有的数需要O(nk)个操作。
最终时间是O(nklogk + n^2klogn) = O(nk(logk+nlogn))。
不知有没有更快的方法。
【在 g*****i 的大作中提到】
: O(n)吧,|a-b| + |b-c| + |c-a| = (Max(abc)-Min(abc))*2,然后每个array排序后一个
: pointer,最小的那组移动.
| d********y
发帖数: 2114 | 6 这个sum of difference怎么定义？
默认是排序后计算的话，这个做法是对的。
【在 d***n 的大作中提到】
: |a-b| + |b-c| + |c-a| = (Max(abc)-Min(abc))*2对n=3成立
: 用这个思路，一般情况还是需要O(n)的时间来计算差和。
: 先对每个array排序时间O(klogk), k是array平均长度。
: 然后根据每个array最小的数对所有array排序时间O(nlogn)。
: scan的时候要维持所有array按当前数的大小排序，每scan一个数需要logn时间调整排序（binary search or heap），计算新的差和O(n), scan完所有的数需要O(nk)个操作。
: 最终时间是O(nklogk + n^2klogn) = O(nk(logk+nlogn))。
: 不知有没有更快的方法。
| r*******y
发帖数: 1081 | 7 Is this true?
asume a1, a2, a3, a4, a5, a6..., an are decreasing, then
|a1 -a2| + |a2 - a3| + ... + |an - a1| = 2*(a1 - an).
Now assume they are 1, -1, 1, -1, 1, -1, ...., 1, -1 which have
2k numbers and n = 2k. At this time the sum should be 2n =
n*(Max - MIN)
So we don't have uniform equation for |a1 - a2| + ... + |an - a1| ?
【在 g*****i 的大作中提到】
: O(n)吧,|a-b| + |b-c| + |c-a| = (Max(abc)-Min(abc))*2,然后每个array排序后一个
: pointer,最小的那组移动.
| d***n
发帖数: 65 | 8 Good point. guangyi's equation only applies to n = 3 case. | d***n
发帖数: 65 | | c*********t
发帖数: 2921 | 10 这道题是什么意思？
1. 是从每个array个各取一个数，sum of their differences is minimum？
2. 还是这 n 个数，可以多个从某一个array里取？如果是这种的话，就把所有的数组
放在一起排序，然后scan一边，就可以了。
谢谢！
minimum.
Here
【在 B*******1 的大作中提到】
: Given n arrays, find n number such that sum of their differences is minimum.
: For e.g. if there are three arrays
: A = {4, 10, 15, 20}
: B = {1, 13, 29}
: C = {5, 14, 28}
: find three numbers a, b, c such that |a-b| + |b-c| + |c-a| is minimum. Here
: the answer is a = 15, b = 13, and c = 14
| i*****e
发帖数: 63 | 11 Good point.
The first thing came into my mind is to find a circle with minimal radius to
include n points.
'Cos all the points are on a single line, I believe the basic idea would be
similar to yours
【在 r*******y 的大作中提到】
: Is this true?
: asume a1, a2, a3, a4, a5, a6..., an are decreasing, then
: |a1 -a2| + |a2 - a3| + ... + |an - a1| = 2*(a1 - an).
: Now assume they are 1, -1, 1, -1, 1, -1, ...., 1, -1 which have
: 2k numbers and n = 2k. At this time the sum should be 2n =
: n*(Max - MIN)
: So we don't have uniform equation for |a1 - a2| + ... + |an - a1| ?
|
|
