厦门免费自助建站模板,北京网页网站设计,景山网站建设,技术支持 佛山网站建设已知由n#xff08;M2#xff09;个正整数构成的集合A{akn},将其划分为两个不相交的子集A1 和A2#xff0c;元素个数分别是n1和n2#xff0c;A1和A2中的元素之和分别为S1和S2。设计一个尽可能高效的划分算法#xff0c;满足|n1-n2|最小且|s1-s2|最大。要求…
已知由nM2个正整数构成的集合A{akn},将其划分为两个不相交的子集A1 和A2元素个数分别是n1和n2A1和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(lowhigh)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;}
}
