手机 网站开发aspx,wordpress 模板调用,钓鱼网页在线生成网站,做网站赚钱平台一、题目
1603. 整数集合划分https://www.acwing.com/problem/content/description/1605/ 二、算法的基本设计思想
由题意知#xff0c;将最小的 个元素放在 中#xff0c;其余的元素放在 中#xff0c;分组结果即可满足题目要求。仿照快速排序的思想#xff0c;基于枢…一、题目
1603. 整数集合划分https://www.acwing.com/problem/content/description/1605/ 二、算法的基本设计思想
由题意知将最小的 个元素放在 中其余的元素放在 中分组结果即可满足题目要求。仿照快速排序的思想基于枢轴将 n 个整数划分为两个子集。根据划分后枢轴所处的位置i分别处理
① 若 i 则分组完成算法结束
② 若 i 则枢轴及之前的元素均属于 继续对 i 之后的元素进行划分
③ 若 i 则枢轴及之后的元素均属于 继续对 i 之前的元素进行划分
基于该设计思想实现的算法无须对全部元素进行全排序其平均时间复杂度是O(n)空间复杂度是O(1)。
三、算法实现
#include iostream
#include algorithm
using namespace std;int setPartition(int a[], int n) {int pivotkey, low 0, low0 0, high n - 1, high0 n - 1, flag 1, k n / 2, i; //pivotkey保存枢轴元素值//low0,high0保存low,high的初值避免丢失进行后续多轮的划分的位置定位int s1 0, s2 0; //记录A1、A2集合各自的和while(flag) {pivotkey a[low]; //选择枢轴while(low high) { //基于枢轴对数据进行划分while(low high a[high] pivotkey) --high; //若数组最右边的值比枢轴的值大说明不需要调整往左移动high继续比较即可if(low ! high) a[low] a[high]; //找到第一个比枢轴元素值小的元素将其调整到前面while(low high a[low] pivotkey) low; //若数组最左边的值比枢轴的值小说明不需要调整往右移动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) { //枢轴及之前的元素均属于A1继续对 low 之后的元素进行划分low0 low;high high0;}else{ //否则枢轴及之后的元素均属于A2继续对 low 之前的元素进行划分high0 --high;low low0;}}}for(i 0; i k; i) s1 a[i]; //计算S1和for(i k; i n; i) s2 a[i]; //计算S2printf(%d %d, (n-k)-k, s2-s1);return s2-s1;
}int main() {int n;cinn;int a[n];for(int i 0;i n; i)cina[i];setPartition(a,n);
}
四、关于快速排序
快速排序是一种常见且高效的排序算法它基于分治的思想。它的基本思想是选择一个基准元素然后将数组分为两个子数组一个子数组中的元素都小于基准元素另一个子数组中的元素都大于基准元素。然后对这两个子数组分别递归地进行快速排序直到整个数组有序。
具体来说快速排序的过程如下
选择一个基准元素通常是数组中的第一个元素。将数组中小于基准元素的元素移到基准元素的左边大于基准元素的元素移到基准元素的右边基准元素放在中间。递归地对基准元素左右两边的子数组进行快速排序。
