已知由n(n≥2)个正整数构成的集合A={ak|0≤k<n),将其划分为两个不相交的子集A1和A2,元素个数分别是n1和n2,A1和A2中元素之和分别为S1和S2,设计一个尽可能高效的划分算法,满足|n1—n2|最小且|S1—S2|最大。 要求: 给出算

admin2017-08-16  39

问题 已知由n(n≥2)个正整数构成的集合A={ak|0≤k<n),将其划分为两个不相交的子集A1和A2,元素个数分别是n1和n2,A1和A2中元素之和分别为S1和S2,设计一个尽可能高效的划分算法,满足|n1—n2|最小且|S1—S2|最大。
要求:
给出算法的基本设计思想。

选项

答案由题意知,将最小的[n/2]个元素放在A1中,其余的元素放在A2中,分组结果即可满足题目要求。仿照快速排序的思想,基于枢轴将n个整数划分为两个子集。 根据划分后枢轴所处的位置i分别处理: ①若i=4[n,2],则分组完成,算法结束; ②若i<[n,2],则枢轴及之前的所有元素均属于A1,继续对j之后的元素进行划分; ③若i>[n,2],则枢轴及之后的所有元素均属于A2,继续对i之前的元素进行划分; 基于该设计思想实现的算法,毋须对全部元素进行全排序,其平均时间复杂度是O(n),空间复杂度是O(1)。

解析
转载请注明原文地址:https://kaotiyun.com/show/eJRi777K
0

最新回复(0)