k***g
发帖数: 166 | 1 有两个大小相同的整数数组A,B
排序B使得sum(|A[i]-B[i]|)最小
怎么做？ |
k***g
发帖数: 166 | |
T********g
发帖数: 15 | 3 这题的意思应该是按照A里面元素的顺序 对B进行排序 |
M***6
发帖数: 895 | |
w*****w
发帖数: 53 | 5 只要两个数组长度一样，那么都从小到大sort一遍，但是要记住原来两个数组的
entries是怎么对应的，比如sort后A组的第0个数是从原来第几个位置移动过来的，B组
的第0个数是从原来第几个数移动过来的。
比如A组第0个数是从原本第5个entry移动过来的，B组排序后的第0个数是从原本第3个
entry移动过来的。那么你需要做的事，就是把B组原本第3个entry的数移动到第5个。
以此类推。
如果不对，那就见笑了 |
z*********n
发帖数: 1451 | 6 sort一遍一一对应一下应该就行了，自己脑子里简单证明了一下，应该能保证sum最小
。看大牛们怎么说？ |
s***d
发帖数: 15421 | 7 恩 没错。
【在 z*********n 的大作中提到】
: sort一遍一一对应一下应该就行了，自己脑子里简单证明了一下，应该能保证sum最小
: 。看大牛们怎么说？
|
l****u
发帖数: 1764 | 8 恩 用一个hashtable记住排前排后的对应关系，然后还原
不过空间复杂度是O(N)
不知道有没有空间复杂度O(1)的
【在 w*****w 的大作中提到】
: 只要两个数组长度一样，那么都从小到大sort一遍，但是要记住原来两个数组的
: entries是怎么对应的，比如sort后A组的第0个数是从原来第几个位置移动过来的，B组
: 的第0个数是从原来第几个数移动过来的。
: 比如A组第0个数是从原本第5个entry移动过来的，B组排序后的第0个数是从原本第3个
: entry移动过来的。那么你需要做的事，就是把B组原本第3个entry的数移动到第5个。
: 以此类推。
: 如果不对，那就见笑了
|
k***g
发帖数: 166 | 9 我也觉得是，但不知道应该怎么证明
【在 z*********n 的大作中提到】
: sort一遍一一对应一下应该就行了，自己脑子里简单证明了一下，应该能保证sum最小
: 。看大牛们怎么说？
|
r*****n
发帖数: 29 | 10 只需要证明一种情况就行:
A
C
Then in all cases |A-C| + |B-D| <= |A-D| + |B-C|
ACDB
ACBD
ABCD
CDAB
CADB
CABD
走一遍就明确了 |
