数据结构
2016-43
已知由 n（n≥2）个正整数构成的集合 A=akmid 0≤ k<n\，将其划分为两个不相交的子集 A1 和 A2，元素个数分别是 n1 和 n2，A1 和 A2 中元素之和分别为 S1 和 S2。设计一个尽可能高效的划分算法，满足 |n1-n2| 最小且 |S1-S2| 最大。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
（3）说明你所设计算法的平均时间复杂度和空间复杂度。
答案
（1）算法基本设计思想
要使两个子集元素个数差最小且和的差最大，应将最小的⌊n/2⌋个元素放入A₁，其余放入A₂。采用快速排序中的划分思想，基于枢轴进行划分，通过非递归方式逐步将数组划分为两部分，使得左半部分恰好包含最小的⌊n/2⌋个元素，右半部分包含剩余元素。最后分别计算两部分的和并返回其差值。
（2）算法描述（C语言）
int setPartition(int a[], int n) {
int pivokey = 0, low = 0, low0 = 0, high = n - 1, high0 = n - 1, flag = 1, k = n / 2, i;
int s1 = 0, s2 = 0;
while(flag) {
pivokey = a[low]; // 选择枢纽
while(low < high) {
while(low < high && a[high] >= pivokey) --high;
if(low != high) a[low] = a[high]; // 替换较大的数
while(low < high && a[low] <= pivokey) ++low;
if(low != high) a[high] = a[low]; // 替换较小的数
}
a[low] = pivokey; // 完成交换枢纽
if(low == k - 1) {
flag = 0;
} else {
if(low < k - 1) {
low0 = ++low;
high = high0;
} else {
high0 = --high;
low = low0;
}
}
}
for(i = 0; i < k; i++) s1 += a[i];
for(i = k; i < n; i++) s2 += a[i];
return s2 - s1;
}（3）时间复杂度与空间复杂度
- 平均时间复杂度：O(n)，期望线性时间完成划分。
- 空间复杂度：O(1)，仅使用常数额外空间。