【2016年数据结构真题】
已知由n（M>2）个正整数构成的集合A={a<k<n},将其划分为两个不相交的子集A1 和A2，元素个数分别是n1和n2，A1和A2中的元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|s1-s2|最大。要求：
1） 给出算法的基本设计思想。
2） 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
3） 说明你所设计算法的平均时间复杂度和空间复杂度。
// 方法一;对整个数组进行排序，然后再将整个数组等分为两份,此时因为利用的是选择排序，所以时间复杂度为O (n^2)
int setpartition(int[] a, int n)
{Selectsort(a, 0, n - 1);int s1 = 0, s2 = 0; //S1,S2表示数组的前半部分和后半部分之和for (int i = 0; i < n / 2; i++)s1 += a[i];for (int i = n / 2; i < n; i++)s2 += a[i];return s2 - s1;
}
void Selectsort(int[] a, int n)
{ //对长度为n的数组a进行选择排序for (int i - 0; i < n - 1; i++){int min = i; //表示本轮次排序中的最小值所在的数组下标for (int j = i + 1; j < n; j++){if (a[j] < a[min])min = j;}int temp = a[i];a[i] = a[min];a[min] = temp;}
}
算法的基本设计思想
-
由题意知，将最小的 n/2 （向下取整） 个元素放在A1中，其余的元素在A2中，分组结果即可满足题目要求。仿照快速排序的思想，基于枢轴将个整数划分为两个子集。根据划分后枢轴所处的位置i分别处理:
- 若i= n/2 （向下取整） ，则分组完成，算法结束;
- 若i< n/2 （向下取整） ，则枢轴及之前的所有元素均属于 A1，继续对 i之后的元素进行划分
- 若i> n/2 （向下取整） ，则枢轴及之后的所有元素均属于 A2，继续对 i之前的元素进行划分
基于该设计思想实现的算法，无须对全部元素进行全排序，其平均时间复杂度是 O(n) 空间复杂度是 0(1)
法二
int setPartition(int a[], int n)
{int pivotkey, low = 0, low0 = 0, high = n - 1, high0 = n - 1, flag = 1, k = n / 2, i;int s1 = 0, s2 = 0;while (flag){pivotkey = a[low]; //选择枢轴while (low < high) //基于轴对数据进行划分{while (low < high && a[high] >= pivotkey)--high;if (low != high)a[low] = a[high];while (low < high && a[low] <= pivotkey)++low;if (low != high)a[high] = a[low]; //end of while(low<high)a[low] = pivotkey;if (low == k - 1) //如果枢纽是第n/2个元素。划分成功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;}
}