1. 问题描述
设S是n个不等的正整数的集合，n为偶数，给出一个算法将S划分为子集S1和S2，使得|S1|=|S2|且达到最大，即两个子集元素之和的差达到最大。(要求：T(n)=O(n))。
2. 解题思路
可参考选择问题（选出A[1,…n]中第k小的元素），所使用的划分法（选择问题的复杂度下限是O(n)）请参见我的另一篇文章复杂度为O(n)的选择问题解法，在本问题中选出第n/2小的元素（类似于中位数m），然后再利用该中位数使用快排中的划分函数partition，小于等于中位数m的元素划分到S1，大于m的划分到S2。这样可保证最终|S1|=|S2|且最终两个子集元素之和的差达到最大。
3. 代码
#include <iostream>
#include <vector>
using namespace std;
class Ques20201007 {
public:
vector<int> arrs = { 2,5,8,4,3,9,10,6,7,1,14,15 }; // n=12 整数
void test() {
int k = arrs.size() / 2; // 选取n/2大小的数
int mid_postion=Select(arrs,0,11, k); // 返回的是中位数的索引
swap(arrs[0],arrs[mid_postion]);
int postion=partition(arrs,0, arrs.size()-1); // 再次划分
// partition可以返回划分元素最终的位置，以此分为两个集合S1 S2
vector<int> S1,S2;
for (int i = 0; i < arrs.size();i++) {
if (i<= postion) {
S1.push_back(arrs[i]);
}
else{
S2.push_back(arrs[i]);
}
}
print();
}
private:
void print() {
for (int i = 0; i < arrs.size();i++) {
cout << arrs[i]<<" ,";
}
}
//Q2. 设S是n个不等的正整数的集合，n为偶数，给出一个算法将S划分为子集S1和S2，使得|S1|=|S2|且
// 即两个子集元素之和的差达到最大。(要求：T(n)=O(n))
// 思路(我的)：可参考选择问题（选出A[1,…n]中第k小的元素），所使用的划分法（选择问题的复杂度下限是O(n)），
//在本问题中选出第n/2小的元素（类似于中位数m）。然后再遍历一遍数组，小于等于中位数m的元素划分到S1，大于m的划分到S2。
//这样可保证最终|S1|=|S2|且最终两个子集元素之和的差达到最大。
int partition(vector<int>& arr, int startIndex, int endIndex) { //选定作划分的数组元素（基准元素）是v=arr[m]
int pivot = arr[startIndex];//取第一个元素当做基准元素
int left = startIndex;
int right = endIndex;
while (left != right) {
while (left<right && arr[right]>pivot) {
right--;// 控制right指针左移
}
while (left < right && arr[left] <= pivot) {
left++;// 从右向左查
}
if (left < right) { // 交换A[i]和A[p]的位置
swap(arr[left], arr[right]);
}
}
//pivot和指针重合点交换
arr[startIndex] = arr[left];
arr[left] = pivot; // 划分元素在位置p,把本来在2位置的划分元素挪到4去。也相当于做一个交换
return left; // 返回基准元素的位置
}
/* 二分法 查找插入位置*/
int searchInsert(vector<int>& Array, int left, int right, int target) //vector是c++中一种容器，可看做数列
{
while (left <= right)
{
int mid = left + (right - left) / 2;
if (Array[mid] == target)
{
return mid;
}
else if (Array[mid] < target)//如果中间值偏小，将初端右移
{
left = mid + 1;
}
else //中间值偏大则终端左移
{
right = mid - 1;
}
}
return left;//如果目标值target比最大值还大，最后left>right，left=nums.size()
//如果比最小值还小，最后left值为0，因为right会先减为-1后与left交换，left=0且比right大，跳出循环且符合题意，目标值变为初端
}
/* 插入排序，时间复杂度是n^2，但是使用二分查找优化后的插入排序复杂度是O(nlogn)*/
void insertSort(vector<int>& arr, int start, int end)
{
int length = end - start + 1;
//将arr[]按升序排列
for (int j = 1; j < length; j++)
{
//利用二分法查找要插入的位置,计算机算法与分析第三章课后练习第二.1题
//int key = arr[j+ times *5];
int key = arr[j + start];
int k = searchInsert(arr, start, j + start, key);//找到需要插入的位置k
// 交换位置
if (k != j + start) {
for (int i = j + start; i > k; i--) {
arr[i] = arr[i - 1];
}
arr[k] = key;
}
}
}
int Select(vector<int>& arr, int m, int p, int k) {// 输入arr[0,...n],k是置顶要输出的第k小的元素
// 将A划分为r(如r=5)个一组，共有n/5(向上取整)个组（取n/5个中位）
// 每组找一个中位数，把它们放到集合M中
// 可使用排序法，时间复杂度为O(c)
// 参数说明：返回一个i值，使得A[i]是A[m..p]中第k小的元素
int n, i, j;
int r = 5;
if (p - m + 1 <= r) {
insertSort(arr, m, p);
return m + k; // m+k是这个的中位数
}
while (true) {
n = p - m + 1;
int t = floor(n / r);
// 新的边界，0-m + floor(n / r)
if (t == 1) {
// 当只有1组时，交换后arr[1]就是中位数了，直接去划分就好
for (int i = 1; i <= 1; i++) {//计算中间值
int right = m + i * r - 1;
insertSort(arr, m + (i - 1) * r, right); // i代表这是第几组
// 将中间值收集到A[m..p]的前部
swap(arr[m + i - 1], arr[m + (i - 1) * r + (int)ceil(r / 2)]);
}
}
else {
for (int i = 1; i <= floor(n / r) + 1; i++) {//计算中间值
int right = m + i * r - 1;
if (i == floor(n / r) + 1) {
right = n - 1;
insertSort(arr, m + (i - 1) * r, right); // i代表这是第几组
// 最后一组元素个数n mod 5
swap(arr[m + i - 1], arr[m + (i - 1) * r + (int)ceil((n % 5) / 2)]);
}
else {
insertSort(arr, m + (i - 1) * r, right); // i代表这是第几组
// 将中间值收集到A[m..p]的前部
swap(arr[m + i - 1], arr[m + (i - 1) * r + (int)ceil(r / 2)]);
}
}
int newright = m + floor(n / r);// 分成了3组就有3个中位数[0,2]再次进行排序，选最终的中位数
// 为什么要将ceil(floor(n/r)/2 中值的中值 作为k传入=>选好的中位数现在排在最前面，还需要再中位数中选出中位数
j = Select(arr, m, newright, ceil(floor(n / r) / 2));// 左边界m,右边界m+floor(n/r)-1，中值的中值
// 这里期望j返回的是什么呢？返回中位数的位置？
swap(arr[m], arr[j]);
}
int midposition = partition(arr, m, p); // 以最终选出的中位数arr[m]，这里中位数已经被收集到前面了作为参照数，将数组s划分为两个部分，使得m所处的位置比左侧的数目大1
if (midposition - m + 1 == k) {// 如果划分后左侧的元素的个数+1后刚好等于k，那么这个中位数就是要找的
return midposition;
}
else if (midposition - m + 1 > k) {
p = midposition - 1;
}
else {
k = k - (midposition - m + 1);
m = midposition + 1;
}
}
}
};
//Ques20200925
int main() {
Ques20201007 cla = Ques20201007();
cla.test();
return 0;
}
4. 运行效果
以中位数6，划分为前面的S1={1,3,2,4,5,6} 以及后面的S2={7,8,9,10,14,15}，这样出来的两集合差值最大，找中位数的过程复杂度为O(n)。
