算法专题七: 分治归并

server/2024/10/21 4:13:55/

目录

  • 1. 排序数组
  • 2. 交易逆序对的总数
  • 3. 计算右侧小于当前元素的个数
  • 4. 翻转对

1. 排序数组

在这里插入图片描述
在这里插入图片描述

算法思路: 本道题使用归并的思路进行排序, 先讲数组分为左右两个区间, 然后合并两个有序数组.

class Solution {vector<int> tmp;
public:vector<int> sortArray(vector<int>& nums) {tmp.reserve(nums.size());mergesort(nums,0,nums.size()-1);return nums;}void mergesort(vector<int>& nums,int left,int right){if(left >= right) return;int mid = (right + left)>>1;mergesort(nums,left,mid);mergesort(nums,mid+1,right);int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right)tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];for(int i = left; i <= right;i++){nums[i] = tmp[i - left];}}
};

2. 交易逆序对的总数

在这里插入图片描述

算法思路:

在这里插入图片描述

先找左半部分的逆序对, 然后再找右半部分的逆序对, 最后再一左一右的找逆序对, 找完左半部分和右半部分之后给数组排个序对数组的结果不影响, 而且排完序之后找一左一右的逆序对还简单些, 不由得我们就可以想到此方法和归并排序的思路一样, 只不过再排序的过程中增加了统计逆序对的个数. 这里可以采用两种策略, 第一种固定当前位置的值, 然后找前面有多少数是比我大的, 第二种策略, 固定当前位置的值, 找后面有多少元素是比我小的.

  • 首先使用第一种策略, 固定一个数, 在前面找比我大的元素的个数.

在这里插入图片描述
当前为升序的排序, 我们归并的时候如果nums[cur1] <= nums[cur2] 时, 此时我们只需要把cur1++就行, 如果nums[cur1]在某一个位置大于nums[cur2]时,此时已经找到了比nums[cur2]大的元素, 那么mid- cur1 + 1这段区间里面的所有值都比nums[cur2]大, 此时统计逆序对的数量即可, 然后再让cur2++, 但是不要往了我们还要排序, 所以这一步写在归并数组那里即可.
那么既然升序可以, 降序可不可以呢?

在这里插入图片描述
如图所示, 该数组为降序的时候, 固定cur1, cur2位置时,如果cur1大于cur2则开始统计cur1中大于cur2元素的个数, 看似没有什么问题, 但是如果进入下一次循环中, cur1++之后还有可能大于cur2,此时在统计那不是重复了嘛, 显然结果是错误的

  • 第二种策略: 固定一个数, 然后找后面比我小的元素的个数

在这里插入图片描述
首先先来看降序的数组, 来统计固定一个位置之后, 后面有多少元素比我小, 当nums[cur1] <= nums[cur2]时, 此时不是我们想要的结果, 我们需要的是nums[cur1]>nums[cur2], 这个时候, 我们统计后面有多少个元素比我小即可, 很显然此时数组是降序的, 所以right - cur2 + 1 即为结果

if(nums[cur1] <= nums[cur2])
tmp[i++] = nums[cur2++];
else
{
ret += right - cur2 + 1;
tmp[i++] = nums[cur1++];
}

反之我们来看一下升序

在这里插入图片描述

此时数组为升序, 我们需要找后面比前面小的元素的个数, 当固定到cur1之后, nums[cur1] > nums[cur2]时, 此时开始找结果, 在后面看在mid到cur2之间的这部分都是比nums[cur1]小的, 但是下一次cur2++之后还有可能是小于nums[cur1]的, 所以此时重复统计了 , 结果是错误的.

代码部分:

策略1

class Solution {int tmp[50000];
public:int reversePairs(vector<int>& record) {return mergeSort(record,0,record.size()-1);}int mergeSort(vector<int>& nums,int left,int right){if(left>=right) return 0;int ret = 0;int mid = (right + left) >> 1;ret += mergeSort(nums,left,mid);ret += mergeSort(nums,mid+1,right);//程序到这里左边与右边已经处理完毕, 现在处理左右int cur1 = left, cur2 = mid + 1, i = 0;//升序 找比当前位置大的个数while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2])tmp[i++] = nums[cur1++];else{ret += mid - cur1 + 1;tmp[i++] = nums[cur2++]; }}while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];for(int i = left; i <= right; i++){nums[i] = tmp[i - left];}return ret;}
};

策略2

class Solution {int tmp[50000];
public:int reversePairs(vector<int>& record) {return mergeSort(record,0,record.size()-1);}int mergeSort(vector<int>& nums,int left,int right){if(left>=right) return 0;int ret = 0;int mid = (right + left) >> 1;ret += mergeSort(nums,left,mid);ret += mergeSort(nums,mid+1,right);//程序到这里左边与右边已经处理完毕, 现在处理左右int cur1 = left, cur2 = mid + 1, i = 0;//降序 找比当前位置小的个数while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2])tmp[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 i = left; i <= right; i++){nums[i] = tmp[i - left];}return ret;}
};

3. 计算右侧小于当前元素的个数

在这里插入图片描述

算法思路:

本道题更上一道题的思路是一模一样的, 上一道题我们采用了策略一的方法, 本道题我们采用策略二, 找后面比当前位置元素小的元素的个数, 但是与上一道题不同的是本道题要求返回对应位置的结果, 这是个问题, 如何解决呢, 我们可以采用哈希的思想, 如果使用哈希表那么如果遇到重复的元素, 我们就无法进行解决, 但是我们可以采用这种思想, 创建一个新的数组, 这个数组中存放的是对应位置原始的下标, 然后这个数组跟着nums一起变化, 但是无论怎样变换, 里面的下标还是最原始的下标位置.

在这里插入图片描述

编写代码:

class Solution {vector<int> index;vector<int> ret;int tmpNums[500010];int tmpIndxt[500010];
public:vector<int> countSmaller(vector<int>& nums) {int n = nums.size();ret.resize(n);index.resize(n);for(int i = 0;i < n;i++)index[i] = i;mergeSort(nums,0,n-1);return ret;}void mergeSort(vector<int>& nums,int left,int right){if(left >= right) return;int mid = (left + right)>>1;mergeSort(nums,left,mid);mergeSort(nums,mid+1,right);//至此左右已经处理完, 现在处理一左一右int cur1 = left, cur2 = mid+1, i = 0;while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2]){tmpNums[i] = nums[cur2];tmpIndxt[i++] = index[cur2++];}else{ret[index[cur1]] += right - cur2 + 1;tmpNums[i] = nums[cur1];tmpIndxt[i++] = index[cur1++];}}while(cur1 <= mid){tmpNums[i] = nums[cur1];tmpIndxt[i++] = index[cur1++];}while(cur2 <= right){tmpNums[i] = nums[cur2];tmpIndxt[i++] = index[cur2++];}for(int i = left; i <= right; i++){nums[i] = tmpNums[i - left];index[i] = tmpIndxt[i - left];}}
};

4. 翻转对

在这里插入图片描述

算法思路:

首先我们还是先考虑两个策略. 策略一, 计算后面有多少个元素的两倍比我小, 策略二. 计算前面有多少元素的一半比我大. 不同于前两题, 本道题无法在归并的时候进行计算, 因为这里的比较逻辑和归并的比较逻辑是不同的, 所以这里我在归并逻辑之前采用双指针的方法先进行统计, 然后在进行归并排序.

在这里插入图片描述

在这里插入图片描述

那么首先来看策略一, 在处理完左右之后并排序之后, 我们处理一左一右的情况, 使用双指针, 计算后面有多少元素的两倍比我小, 如果nums[cur1] <= nums[cur2] * 2, 则说明后面元素的两倍比我大, 那么继续移动cur2, 知道找到cur2的位置两倍比我小, 然后进行统计, 此时cur1++, 进行下一次的统计, 这里cur2还需要回退到mid+1的位置嘛?
答案是不需要的, 因为当前位置cur2位置前面元素的两倍都是比我大的, 那cur1++之后降序, 那么一定也是比我大的, 所以直接统计就可以了, 所以整体的时间复杂度为O(NlogN).

class Solution {int tmp[50000];
public:int reversePairs(vector<int>& nums) {return mergeSort(nums, 0 , nums.size() - 1);}int mergeSort(vector<int>&nums, int left , int right){if(left >= right) return 0;int ret = 0;int mid = (left + right) >> 1;ret += mergeSort(nums,left,mid);ret += mergeSort(nums,mid+1,right);int cur1 = left, cur2 = mid + 1, i = left;while(cur1 <= mid){while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;if(cur2 > right) break;//小优化ret += right - cur2 + 1;cur1++;}//降序cur1 = left, cur2 = mid + 1;while(cur1 <= mid && cur2 <= right)tmp[i++] = nums[cur1] >= nums[cur2] ? nums[cur1++] : nums[cur2++];while(cur1<=mid) tmp[i++] = nums[cur1++];while(cur2<=right) tmp[i++] = nums[cur2++];for(int j = left; j <= right; j++)nums[j] = tmp[j]; return ret;}
};

策略二: 找前面有多少元素的一半比我大

在这里插入图片描述

其实更策略一的逻辑是类似的, 只不过这里的数组是升序排列的, 找前面有多少元素的一半比我大, 先让cur1走, 如果/2之后大于nums[cur2]则, cur1++, 找到位置之后统计ret, 然后让cur2++,进行下一次的统计, 此时cur1也不需要回去, cur1之前的位置一半都是比cur2小的, 那么cur2++之后一定还是比cur1小, 所以cur2直接++即可.

class Solution {int tmp[50000];
public:int reversePairs(vector<int>& nums) {return mergeSort(nums, 0, nums.size()-1);}int mergeSort(vector<int>& nums,int left, int right){if(left >= right) return 0;int mid = (left + right) >> 1;int ret = 0;ret += mergeSort(nums,left,mid);ret += mergeSort(nums,mid+1,right);int cur1 = left, cur2 = mid + 1, i = left;//升序, 先统计逆序对while(cur2 <= right){while(cur1 <= mid && nums[cur1] / 2.0 <= nums[cur2]) cur1++;if(cur1 > mid) break;ret += mid - cur1 + 1; cur2++;} //合并有序数组cur1 = left, cur2 = mid + 1;while(cur1 <= mid && cur2 <= right)tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];for(int j = left ; j <= right ; j++)nums[j] = tmp[j];return ret;}
};

完


http://www.ppmy.cn/server/133529.html

相关文章

wifi、热点密码破解 - python

wifi、热点密码破解 - python

乐子脚本&#xff0c;有点小慢&#xff0c;试过多线程&#xff0c;系统 wifi 连接太慢了&#xff0c;需要时间确认&#xff0c;多线程的话系统根本反应不过来。 也就可以试试破解别人的热点&#xff0c;一般都是 123456 这样的傻鸟口令 # coding:utf-8 import pywifi from pyw…
阅读更多...
python 打包为动态链接库(.so文件)

python 打包为动态链接库(.so文件)

参考资料&#xff1a;https://medium.com/yeap0022/linux-compress-python-packages-into-shared-library-so-8342bffab001 注意事项&#xff1a;.py, .c后缀文件都可以删掉&#xff0c;cache也可以删掉&#xff0c;但是__init__.py文件不能删&#xff0c;建立的子文件夹也不能…
阅读更多...
JavaWeb环境下Spring Boot在线考试系统的优化策略

JavaWeb环境下Spring Boot在线考试系统的优化策略

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了基于JavaWeb技术的在线考试系统设计与实现的开发全过程。通过分析基于Java Web技术的在线考试系统设计与实现管理的不足&#xff0c;创建了一个计算机管理基于Ja…
阅读更多...
Android——通过MediaStore查询图片

Android——通过MediaStore查询图片

查询图片&#xff1a; private void loadImageList() {String[] columns new String[]{MediaStore.Images.Media._ID, // 编号MediaStore.Images.Media.TITLE, // 标题MediaStore.Images.Media.SIZE, // 文件大小MediaStore.Images.Media.DATA, // 文件路径};Cursor cursor g…
阅读更多...
基于FPGA的以太网设计（四）

基于FPGA的以太网设计（四）

1.ARP协议简介 ARP&#xff08;Address Resolution Protocol&#xff09;&#xff0c;即地址解析协议&#xff0c;是根据IP地址&#xff08;逻辑地址&#xff09;获取MAC地址的一种TCP/IP协议。在以太网通信中&#xff0c;数据是以“帧”的格式进行传输的&#xff0c;帧格式里…
阅读更多...
零代码快速开发智能体 ｜甘肃旅游通

零代码快速开发智能体 ｜甘肃旅游通

在互联网信息爆炸的时代&#xff0c;寻找一处让人心动的旅游胜地往往需要花费大量的时间和精力。而今天&#xff0c;我要向大家介绍一款能够帮助你轻松规划甘肃之行的智能体——“甘肃旅游通”。这款智能体通过低代码开发&#xff0c;集合了丰富的旅游信息和个性化推荐功能&…
阅读更多...
单片机裸机程序 —— 设计模式

单片机裸机程序 —— 设计模式

目 录 软件设计模式的用途一、轮询模式二、前后台模式三、时间片模式四、状态机模式 软件设计模式的用途 专业的程序员不会在知道需求后&#xff0c;马上脑热地去敲代码&#xff0c;然后一边调试一边修复bug。好习惯是把前期工作做好再开始敲键盘&#xff0c;比如选定一个合适…
阅读更多...
【Spring】获取Cookie和Session（@CookieValue()和@SessionAttribute()）

【Spring】获取Cookie和Session（@CookieValue()和@SessionAttribute()）

获取 Cookie 传统获取 Cookie 这是没有 Spring 的时候&#xff0c;用 Servlet 来获取&#xff08;获取所有的 Cookie&#xff09; Spring MVC 是基于 Servlet API 构建的原始 Web 框架&#xff0c;也是在 Servlet 的基础上实现的 RequestMapping("/getcookie") …
阅读更多...
最新文章

Copyright @ 2022~2023