同一产品做多个网站,哪个网站上网好,公司网站搜索不到,软件制作工程师“别让自我被拯救~” 谈谈归并与分治 当我们首次接触排序算法时#xff0c;一定对所谓 归并方式排序的算法感到头疼~ 因为#xff0c;我们难以形象出其不断 分离时#xff0c;各个区域的状态。然而#xff0c;即便 归并排序算法的学习…
“别让自我被拯救~” 谈谈归并与分治 当我们首次接触排序算法时一定对所谓 归并方式排序的算法感到头疼~ 因为我们难以形象出其不断 分离时各个区域的状态。然而即便 归并排序算法的学习是艰难但掩盖不住其相较于其他算法而言拥有更优时间复杂度而迫使我们不得不盯着头疼的代码苦思冥想。并且归并思想不仅仅体现在排序中更能成为我们解决实际问题时的一个方略方法。 归并核心之一就在于 分治,那么啥子叫 分治? 简单来说就是 分而治之大事化小 。 假设我们要对举例数组元素进行升序排序arr[8] { 6,1,2,7,3,4,8,0}。要排升序需不需要知道每个数与每个数之间的大小关系需要 所以我们得从 n1 开始与 n-1个数进行大小关系的比较~ 唔这一套下来直接给时间复杂度 干上了 O(N^2)与冒泡的效率难分伯仲了。 或许我们可以缩小比较范围与n个数比较换成与 n / 2 个数比较呢 或者 n / 4个数 甚至 n1。 归并 vs 快排 快排与归并都是通过在既定区间对数组内元素值进行排序但两者有根本上的区别~ 排序数组 没什么好解析题目的咱们直接以归并的思想拿这道题练练手~ 递归版本:
class Solution {
public:void _MergeSort(vectorint nums,int l,int r,vectorint tmp){// 当归并的区间不存在~if(l r) return;// 划分区域int mid (l r) 1;// 进行左右区间划分分治 -- 我们就认为MergeSort可以给我们完成划分分治工作_MergeSort(nums,l,mid,tmp);_MergeSort(nums,mid1,r,tmp);// 走到这里说明 分治已经做完~ 此时开始归并了// 此时区域被划分为 {l,mid} {mid1,l} // 我们需要保证归并数组的 有序性 所以我们得将这两个区间归并排序// 我们额外的数组起作用了~int begin1 l,end1 mid;int begin2 mid1,end2 r;int index_tmp l; // 注意tmp模拟的是nums 所以这里的index不能为0 根据你的区域划分l设置初始值while(begin1 end1 begin2 end2){if(nums[begin1] nums[begin2]) tmp[index_tmp] nums[begin1];else tmp[index_tmp] nums[begin2];}while(begin1 end1) tmp[index_tmp] nums[begin1];while(begin2 end2) tmp[index_tmp] nums[begin2];//我们现在只是将排序好的数组放在了 tmp 现在我们需要将这些元素 放置回去// 防止多少呢 tmp归并了多少: index_tmp// 从哪里开始放呢 l// for(int il;iindex_tmp;i) nums[i] tmp[i];memcpy(nums[0] l,tmp[0] l,sizeof(int) * (r-l1));}void MergeSort(vectorint nums,int l,int r){vectorint tmp(nums.size());_MergeSort(nums,l,r,tmp);}vectorint sortArray(vectorint nums) {MergeSort(nums,0,nums.size()-1);return nums;}
};
非递归版本: 有些时候考虑堆栈递归的深度可能会要求使用非递归的方式实现归并排序~我们可以使用希尔排序的思想依据gap的间距划分待排序区间~ 算法思想: 不过与 shell排序明显不同的地方是其gap间距尽可能从大值选取,逐渐减小在归并中初始取gap值为1,gap值逐渐增大。 当然这就对应了 递归版的将左右区间缩减到1个元素 细节问题: class Solution {
public:void _MergeSort(vectorint nums, int start1, int end1,int start2, int end2, vectorint tmp){int index_tmp start1;int begin start1;while (start1 end1 start2 end2){if (nums[start1] nums[start2]) tmp[index_tmp] nums[start1];else tmp[index_tmp] nums[start2];}while (start1 end1) tmp[index_tmp] nums[start1];while (start2 end2) tmp[index_tmp] nums[start2];for (int i begin;i index_tmp;i) nums[i] tmp[i];}void MergeSort(vectorint nums, int l, int r){vectorint tmp(nums.size());int gap 1;while (gap nums.size()){for (int i 0;i nums.size();i 2 * gap){// 为什么需要-1 这里是为了满足 [1,1]归并int start1 i, end1 i gap - 1;int start2 i gap, end2 i 2 * gap - 1;// 越界if (end1 r || start2 r) break;// 不足if (end2 r) end2 r;// 进行归并_MergeSort(nums, start1, end1, start2, end2, tmp);}gap * 2;}}vectorint sortArray(vectorint nums) {MergeSort(nums, 0, nums.size() - 1);return nums;}
}; 排序链表 区别于数组排序我们可以通过拿到数组的首元素地址从而访问所有的元素值如果想要交换两个元素的位置直接使用库函数 std::swap()。但现在我们需要排序的数链表其节点内部包含着val我们不能像数组那样对齐进行随机访问所以意向使用快排或者shell完成对题目规定内O(N*LOGN)是行不通的~\
细节问题: 所以我们把目光聚焦在归并排序~ 区别于数组排序我们可以通过俩左右下标计算出mid划分区域在归并排序中我们借助快慢指针完成对前后区域的划分~ class Solution {
public:ListNode* MergeSort(ListNode* head){if(head nullptr || head-next nullptr) return head;ListNode* fast head-next,*slow head;while(fast fast-next){slow slow-next;fast fast-next-next;}// 这里进行切断ListNode* mid slow-next;slow-next nullptr;// 分治ListNode* start1 MergeSort(head);ListNode* start2 MergeSort(mid);// 归并ListNode* newhead new ListNode(-1);ListNode* tail newhead;while(start1 start2){if(start1-val start2-val){tail-next start1;start1 start1-next;}else{tail-next start2;start2 start2-next;}tail tail-next;}// 归并剩下的tail-next start1 nullptr ? start2 : start1;tail newhead-next;delete newhead;return tail;}ListNode* sortList(ListNode* head) {return MergeSort(head);}
}; 合并K个升序链表 一个很简单的思路就是给数组内的链表节点继续排升序。我们可以利用 优先级队列,把vector中的所有元素插入进该数组构建小堆。这样我们每次取堆顶数据时都可以取到最小值从而实现所谓的合并~
class Solution {
public:ListNode* mergeKLists(vectorListNode* lists) {// 这里我们需要重载比较函数 因为默认函数greater不支持auto func [](ListNode* node1,ListNode* node2)-bool{return node1-val node2-val;};// 构建小堆priority_queueListNode*,vectorListNode*,decltype(func) heap;for(auto l:lists) if(l) heap.push(l);ListNode* newhead new ListNode(-1);ListNode* tail newhead;while(!heap.empty()){ListNode* front heap.top();heap.pop();tail-next front;tail tail-next;if(front-next) heap.push(front-next);}tail newhead-next;delete newhead;return tail;}
}; 考虑优先级队列中的个数是既定的k(数组里的首元素)个一个节点的插入、删除花费的时间复杂度为 O(logK)总的效率控制在O(kn * logK)。 再次来会看题目: 嘶~ 这难道不就是叫我们进行区间合并嘛 我们似乎在哪里做过~ 是的 归并排序中当我们进行区域分治后就是区域排序 然而现在更为简单区域是给你划分好了就连区域内的元素也是给你按 升序排序的我们目前要做的无非就是 合并
class Solution {
public:ListNode* mergeList(ListNode* left,ListNode* right){// left||right都可能出现nullptr 即是 不能组成归并的 直接返回 不为空的if(left nullptr) return right;if(right nullptr) return left;ListNode* newhead new ListNode(-1);ListNode* tail newhead;while(left right){if(left-val right-val){tail-next left;left left-next;}else{tail-next right;right right-next;}tail tail-next;}if(left) tail-next left;if(right) tail-next right;tail newhead-next;delete newhead;return tail;}ListNode* _mergeKLists(vectorListNode* lists,int l,int r){if(l r) return nullptr;// 如果只存在一组 直接返回这个链表if(l r) return lists[l];int mid (lr) 1;// 划分为极小的ListNode* left _mergeKLists(lists,l,mid);ListNode* right _mergeKLists(lists,mid1,r);// 进行两两归并return mergeList(left,right);}ListNode* mergeKLists(vectorListNode* lists) {return _mergeKLists(lists,0,lists.size()-1);}
}; 交易逆序对的总数 所谓逆序对就是指: 前后数存在大小关系大的在前小的在后。我们要做的就是统计符合条件的逆序对的个数~ 正如图示我们可以采用暴力解法从i0开始套两层的for循环可以暴搜完成逆序对总数的查找和统计。 int ret 0;for(int i0;in;i)for(int ji1;jn;j){if(nums[i] nums[j]) ret;} 哈哈哈不过多数时候或许压根任何时候刷题软件的后端使用到的令人发指的测试数据往往会让你的代码经不起半点抗击打而原形毕露—— 超过时间限制。 或许我们可以在暴搜的基础上做出一定的优化暴搜花费的时间在哪里你这难道不是说屁话嘛不就是那咔咔两行敲上去的双层for。对 ! 这是原因但这只是表象而非根因~ 在暴搜的过程中并没有保存之前元素艰难爬行于那千疮百孔般代码所留下的记录它们的贡献被历史遗忘.... 当然,本题并不会按照这样的思路解题但却是为探索新方法提供了别样的视角~ 那么回归本题咱们又该从哪些地方下手
为什么选择归并 这与我们归并的过程几乎一样~ 我们引入一个mid指针就会将整个数组分为两个部分。逆序对如何产生呢它可能来自:左半边数组、也可能来自右半边数组、还可能一个来自左半数组另一个来自右半数组...所以一旦我们想要求整个数组的逆序对就将这三种情况相加即可~ 先求左半数组逆序对、再求右半数组、最后是左、右逆序对这就同归并排序一样先排序左边数组、再继续右边数组的排序最后进行归并。我们可以在这个过程中顺便将左、右两边的逆序对求出来最后把这些结果相加即可~
为什么可行? 我们在归并之前就已经统计完成了逆序对并且归并带来的有序性能让我们快速统计出左、右部分数组的逆序对而不需要像暴搜那样枚举所有的情况~ ######### 按照升序排 #############
class Solution {
public:vectorint tmp;int mergesort(vectorint nums,int left,int right){// 不存在的逆序对if(left right) return 0;int mid (left right) 1, ret 0;// 加左、右两边ret mergesort(nums,left,mid);ret mergesort(nums,mid1,right);// 合并数组的情况下:统计ret 左、右部分// 如果是升序 -- 找右半小值int cur1 left,cur2 mid 1,i left;while(cur1 mid cur2 right){if(nums[cur1] nums[cur2]){//找大值// 这里赋值给tmp是满足归并tmp[i] nums[cur1];}else{// 进行更新 统计右半区ret mid - cur1 1;tmp[i] nums[cur2]; // cur2小进入先进入合并}}// 处理剩余数组while(cur1 mid) tmp[i] nums[cur1];while(cur2 right) tmp[i] nums[cur2];// 归并for(int ileft;iright;i) nums[i] tmp[i];return ret;}int reversePairs(vectorint record) {tmp.resize(record.size());return mergesort(record,0,record.size()-1);}
};######### 按照降序排 #############
class Solution {
public:vectorint tmp;int mergesort(vectorint nums,int left,int right){// 不存在的逆序对if(left right) return 0;int mid (left right) 1, ret 0;// 加左、右两边ret mergesort(nums,left,mid);ret mergesort(nums,mid1,right);// 合并数组的情况下:统计ret 左、右部分// 如果是降序 --- 找左边值int cur1 left,cur2 mid 1,i left;while(cur1 mid cur2 right){if(nums[cur1] nums[cur2]){// 不行cur2太大了 完完全全统计不了rettmp[i] nums[cur2];}else{// 统计右半区ret right - cur2 1;tmp[i] nums[cur1];}}// 处理剩余数组while(cur1 mid) tmp[i] nums[cur1];while(cur2 right) tmp[i] nums[cur2];// 归并for(int ileft;iright;i) nums[i] tmp[i];return ret;}int reversePairs(vectorint record) {tmp.resize(record.size());return mergesort(record,0,record.size()-1);}
};本篇到此结束感谢你的阅读
祝你好运向阳而生~
