再问数组分割, 这种简单解法是否正确
本帖最后由 youyou1912 于 2013-04-21 17:42:46 编辑 一个2n的整数数组，分成n元素两组，保证两组和之差的绝对值最小
设计算法，保证两组和之差的绝对值最小。
编程之美上的一题. 解法说的也很清楚. 动态规划解法, 复杂度为 O(N^2 * SUM)
也有人提了新思路
http://blog.sina.com.cn/s/blog_66223402010164ux.html
我也有一个很简单的思路, 不晓得是否正确.
时间复杂度只有O(N*LogN), 空间O(N)
思路就是
假设: 全部数字>=0.
1. 降序排序
2. 两个子数组A,B, 开始遍历排序好的数组, 两个数组的和, 谁小就分配给谁,
3. 一直分配到结束或者其中一个数组个数为n为止.
4. 如果一个数组个数到n, 则剩下的都属于另外一个数组.
举例:
101,88,87,10,9,8,1,1,1,1 (2n=10, n=5)
1. A: {101}, SumA=101, B={88}, SumB=88 (101->A, 88->B)
2. A: {101}, SumA=101, B={88, 87}, SumB=175 (SumA>SumB, 87->B)
3. A: {101,10}, SumA=111, B={88, 87}, SumB=175 (SumA<SumB, 10->B)
.......
5. A: {101, 10, 9, 8, 1}, B:{88, 87}
6. A: {101, 10, 9, 8, 1} SumA=129, B:{88, 87, 1,1,1}, SumB=178, Delta=49
时间复杂: 排序O(N*LogN)+遍历分配O(N)
以上算法基于所有数字>=0, 如果有负数, 可以预处理都+最小负数的绝对值来改为正数, 思路一样.
请教各位, 以上算法是否正确? 算法 编程之美 数组分割
[解决办法]
只要近似的话还可以凑数。最优的话肯定不对
100 80 80 60 41 1
