有一无序,个数为2n的正整数数组,要求将其拆分为元素个数为n的两个数组,并使两个子数组的和最接近。
我想的是设2n的和为sum,取2n中的n个数
对这n个数求和,只用讨论当这n个数小于sum/2 时,最接近的数组。请问如何用stdio.h为头文件实现,谢谢了。另外我这个思路中时间复杂度和空间复杂度都是n!吗,这个也不懂。
下面是一个示例 c++ 代码,实现了这个需求:
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;
int main() {
// 数组中元素个数为2n
int n = 10;
int arr[2 * n] = {10, 5, 12, 6, 7, 8, 15, 20, 25, 30, 40, 45, 50, 55, 60};
// 先对数组进行排序,以便找到相差最小的元素
sort(arr, arr + 2 * n);
// 将数组分成两部分,并计算和
int sum1 = accumulate(arr, arr + n, 0);
int sum2 = accumulate(arr + n, arr + 2 * n, 0);
// 输出和
cout << "sum1 = " << sum1 << endl;
cout << "sum2 = " << sum2 << endl;
return 0;
}
需要注意的是,由于是无序的数组,所以得到的两部分的和可能并不是最优的。但是,这种方法的时间复杂度为 O(nlogn),相对于其他算法来说,是比较优秀的。