【基础算法总结】分治--快排+归并

news/2024/9/29 18:40:13/

目录

  • 一，分治算法介绍
  • 二，算法原理和代码实现
    • 75.颜色划分
    • 912.排序数组-快速排序
    • 215.数组中的第k个最大元素(快速选择算法)
    • LCR159.最小的k个数(快速选择算法)
    • 912.排序数组-归并排序
    • LCR170.数组中的逆序对
    • 315.计算右侧小于当前元素的个数
    • 493.翻转对
  • 三，算法总结

一，分治算法介绍

分治是一类十分重要的算法，"分治"顾名思义就是分而治之，把一个大问题分成若干个相同或是相似的子问题 ，再把这些小问题继续划分成若干个相同或是相似的更小子问题…直到最小子问题不可再划分。接着通过解决最小子问题进而解决了上一层更小子问题…又进而解决了大问题。这个过程就是 – 递归。

我们学过的快速排序和归并排序就是非常典型也是非常重要的分治。但是它们的分治思想不仅仅用于排序上，在解决其他问题时也是非常有效的。下面介绍的若干道题目就是使用快排和归并的核心思想解决的，让大家加深对它们的理解。

二，算法原理和代码实现

leetcode.cn/problems/sort-colors/" rel="nofollow">75.颜色划分

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

这道题十分经典，它的代码是快速排序的核心代码之一(因为快排有多种实现方式，核心代码也有多种)，它的本质就是数组分三块(数组划分)。
本题是为下面几题做铺垫的，不是用分治算法，而是使用三指针。
(1) 首先是三个指针的作用：
i：遍历扫描数组，初始化为0
left：标记0区域的最右侧，初始化为-1
right：标记2区域的最左侧，初始化为最后一个元素的下一个位置。
(2) 这三个下标把数组分为4部分：
[0,left] ：全是0
[left+1,i-1]：全是1
[i,right-1]：待扫描的元素
[right, n-1]：全是2
在这里插入图片描述
(3) 在扫描过程中：
a. 当arr[i] == 0时：swap(arr[++left],arr[i++])，把0放入指定区域，并完成指针移动
b. 当arr[i] == 1时：i++
c. 当arr[i] == 2时：swap(arr[–right],arr[i])，把2放入指定区域，但是i不能移动，因为交换后 i 所指的依旧是待扫描的。
(4) 当 i 与 right 相遇后，待扫描区间不存在了，此时遍历结束。

代码实现：

class Solution 
{
public:void sortColors(vector<int>& nums){int n = nums.size();int left = -1, right = n, i = 0;// 当i >= right时，说明待扫描区域已经扫描完了，可以结束了while(i < right){if(nums[i] == 0) swap(nums[++left], nums[i++]);else if(nums[i] == 1) i++;else swap(nums[--right], nums[i]);}}
};

leetcode.cn/problems/sort-an-array/" rel="nofollow">912.排序数组-快速排序

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

算法原理：

这道题可以使用我们以前学过的快速排序的算法(二路快排)解决，但是当数据中有很多重复值时，使用以前的算法时间复杂度会退化成 O(N^2)。
我们上一题介绍的"数组分三块"(三路快排)的思想就可以很好的解决这个问题，原因是当数组里的数据都是 key 时，进行一次划分后就变成一块区域了(就是等于key的，没有大于或是小于key的)，此时没有左右区间，就不用进行递归了，直接结束。这里的时间复杂度是 O(N) 级别。

这里还可以进行优化：用随机的方式选择基准元素。
在这里插入图片描述

代码实现：

class Solution 
{
public:vector<int> sortArray(vector<int>& nums) {srand(time(NULL)); // 种随机数种子qsort(nums, 0, nums.size()-1);return nums;}void qsort(vector<int>& nums, int l, int r){if(l >= r) return;// 数组分三块(三路快排)int key = getRandom(nums, l, r);int i = l, left = l-1, right = r+1; // 注意这里的初始化值while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]);}// 走完一遍"数组分三块"时，i与right已经重合了// [l, left] [left+1, right-1] [right, r]qsort(nums, l, left);qsort(nums, right, r);}int getRandom(vector<int>& nums, int left, int right){int r = rand();return nums[r % (right - left + 1) + left];}
};

leetcode.cn/problems/kth-largest-element-in-an-array/description/" rel="nofollow">215.数组中的第k个最大元素(快速选择算法)

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

topK问题是一类很重要的问题，一般有4种问法：
a. 找第K大
b. 找第K小
c. 找前K大
d. 找前K小
解决这类问题有两种算法：
(1) 堆结构 – O(N * logN)
(2) 快速选择算法(基于快排) – O(N)

算法原理：

这道题是基于上一题的快排算法内容，由前文可知，基准值 key 把数组分为三块区域，从左往右依次是小于key，等于key，大于key。所以我们只需要确定本题中要找的的第 k 大元素落在哪个区域，就在哪块区域里找，其余两块区域不需要再考虑了。

所以接下来的重点就是要讨论如何确定第 k 大元素落在哪个区域？
假设数组中的三块区域的元素的个数分别是 a，b，c。分三种情况讨论：
在这里插入图片描述
(1) 如果是落在最右边的区域，则 c >= k。
此时只需要去 [right, r] 区域，继续找第 k 大元素就好了。
(2) 如果是落在中间的区域，则 b+c >= k。
此时第 k 大元素一定是在中间的区域，直接返回 key 即可。
(3) 如果(1)(2)都不成立，此时要去 [l, left] 区域，找第 k-b-c 大的元素。

代码实现：

class Solution 
{
public:int findKthLargest(vector<int>& nums, int k) {srand(time(NULL));return qsort(nums, 0, nums.size()-1, k);}int qsort(vector<int>& nums, int l, int r, int k){if(l == r) return nums[l];// 找数组里的随机数做基准值int key = getRandom(nums, l, r);// 数组分三块int left = l - 1, right = r + 1, i = l;while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]);}// 分情况讨论int c = r - right + 1, b = right - left -1;if(c >= k) return qsort(nums, right, r, k);else if(b + c >= k) return key;else return qsort(nums, l, left, k-b-c);}int getRandom(vector<int>& nums, int left, int right){return nums[rand() % (right - left + 1) + left];}
};

leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/" rel="nofollow">LCR159.最小的k个数(快速选择算法)

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

算法原理：

这道题也是一道topk问题，解法也有多种：一是直接排序，再取出前k个元素，时间复杂度O(N * ogN)，二是使用堆结构，时间复杂度O(N * logN)，三是使用快速选择算法，时间复杂度O(N)。

这里只介绍快速选择算法。本题的算法原理和上一题基本上是一模一样的，此处不再详细分析了。简略分析如下：
在这里插入图片描述

细节问题：

根据算法原理可知，快速选择完之后，我们并没有把数组排序，只是把最小的k个数扔到了数组前面，数组还是无序的。

代码实现：

class Solution 
{
public:vector<int> inventoryManagement(vector<int>& stock, int cnt) {srand(time(NULL));qsort(stock, 0, stock.size()-1, cnt);return {stock.begin(), stock.begin() + cnt};}void qsort(vector<int>& nums, int l, int r, int k){if(l >= r) return;// 在数组里找随机值做keyint key = getRandom(nums, l, r);// 数组分三块int left = l - 1, right = r + 1, i = l;while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]);}// 分情况讨论// [l, left] [left+1, right-1] [right, r]int a = left - l + 1, b = right - left -1;if(a > k) qsort(nums, l, left, k);else if(a+b >= k) return;else qsort(nums, right, r, k-a-b);}int getRandom(vector<int>& nums, int left, int right){return nums[rand() % (right - left + 1) + left];}
};

leetcode.cn/problems/sort-an-array/description/" rel="nofollow">912.排序数组-归并排序

算法原理：

归并排序的大致过程：
先取中间点把数组分为两个区间，要把数组排有序，只要左区间有序，右区间有序了，数组就有序了。所以再递归左区间，取中间点把左区间分又为左右两个区间…一直递归，直到左右区间只剩一个元素不可再分割了，这一层进行回退归并过程，归并的核心就是合并两个有序数组，一直归并到第一层，再进行递归右区间…
图解如下：
在这里插入图片描述

细节问题：

这里执行归并操作合并两个有序数组时需要创建临时数组，有两种创建方式：
(1) 边递归边创建
在这里插入图片描述
(2) 提前创建好，并且开好空间(推荐)
在这里插入图片描述

代码实现：

class Solution 
{vector<int> tmp; // 定义为全局
public:vector<int> sortArray(vector<int>& nums) {tmp.resize(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 ) / 2;//int mid = (left + right) >> 1;// 把左右区间排序// [left, mid] [mid+1, right]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];}
};

leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/" rel="nofollow">LCR170.数组中的逆序对

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

算法原理：

这道题比较难。在使用归并分治思想解决这个问题前，先来搞定几个铺垫知识：
(1) 总对数 = 左半区间逆序对个数a + 右半区间逆序对个数b + 左选一个右选一个组成的逆序对个数c。
再对第一个知识进行延伸：
(2) 在左半区间找出逆序对个数a后，进行排序，右半区间找出逆序对个数b后，也进行排序，最后再左选一个右选一个组成的逆序对个数c，也跟着排序，此时 a + b + c = 总对数。

有了上面两点铺垫知识，就可以引出归并排序的算法了：
把整个数组按中点分成两部分，可以在递归中完成左右两区间逆序对个数的计算，同时进行排序，核心过程是如何计算左选一个右选一个组成的逆序对个数，加排序？如果数组有序，可以统计出一大堆。

策略1：用升序，找到该数之前，有多少个数比我大。盯着 cur2 看。
此时是在归并过程中，已经定义了 cur1 和 cur2，分情况讨论：
(1) nums[cur1] <= nums[cur2] -> 此时不能确定左边有多少个数比 nums[cur2]大，cur1++。
(2) nums[cur1] > nums[cur2] -> ret += (mid - cur1 + 1) 个对，一次统计出来一堆，再 cur2++。
在这里插入图片描述

拓展内容：

策略1中，能否用降序，找到该数之前，有多少个数比我大。也盯着 cur2 看？ 不可行。
原因：此时在归并过程中，[left, cur1-1] 区间的数都比 nums[cur1] 要大，[mid+1, cur2-1] 区间的数都比 nums[cur2] 要大，如果我们计算 cur1-1 - left +1 的个数，那在 cur1++ 后又要重新计算前面的个数了。
在这里插入图片描述

策略2 ：用降序，找到该数之后，有多少个数比我小。盯着 cur1 看
(1) nums[cur1] <= nums[cur2] -> 此时不能确定左边有多少个数比nums[cur2]小，cur2++。
(2) nums[cur1] > nums[cur2] -> ret += (right - cur2 + 1)个对，一次统计出来一堆，再 cur1++。
在这里插入图片描述

代码实现：
这里用的是策略1的升序。

class Solution 
{vector<int> tmp;
public:int reversePairs(vector<int>& nums) {tmp.resize(nums.size());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;// 左边的个数+排序  右边的个数+排序// [left, mid] [mid+1, right]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 j = left; j <= right; j++)nums[j] = tmp[j-left];return ret;}
};

策略1和策略2的代码差异：
策略1：升序

在这里插入图片描述

策略2：降序

在这里插入图片描述

leetcode.cn/problems/count-of-smaller-numbers-after-self/description/" rel="nofollow">315.计算右侧小于当前元素的个数

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

算法原理：

这题的本质和上一题一样也是计算逆序对的个数，所以也是使用归并分治的思想。
因为这道题是求右侧小于当前元素的个数，所以用的是上一题的策略2降序。
在这里插入图片描述

但是这道题与上一题不同的是：
我们统计出个数之后，不是直接 ret+= 返回，而是要把个数存入另一个数组的和这个元素对应(原始下标)的位置上。
所以这里我们还要解决一个问题就是：
当统计出 nums[cur1] 的后面有多少个元素比它小之后，还要能找到这个元素的原始下标(在递归过程中cur1是会移动的)。
解决方法：
搞一个与原数组nums同规模的 index 数组，里面的值存的是原数组中每个元素的下标。然后不管nums数组里的元素怎么移动，index 数组里面的值都与它绑定一起移动。
在这里插入图片描述

代码实现：

class Solution 
{vector<int> ret;vector<int> index;int tmpNums[500010];int tmpIndex[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;// [left, mid] [mid+1, right]// 左右区间的个数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];tmpIndex[i++] = index[cur2++];}else{ret[index[cur1]] += right - cur2 + 1; tmpNums[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}}// 处理剩下的排序过程while(cur1 <= mid){tmpNums[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}while(cur2 <= right){tmpNums[i] = nums[cur2];tmpIndex[i++] = index[cur2++];}// 还原for(int j = left; j <= right; j++){nums[j] = tmpNums[j-left];index[j] = tmpIndex[j-left];}}
};

leetcode.cn/problems/reverse-pairs/" rel="nofollow">493.翻转对

在这里插入图片描述
在这里插入图片描述
算法原理：

这道题是个逆序对的变式题，但是它不能和 [LCR170.数组中的逆序对] 一样在归并过程中统计翻转对的个数。因为在那道题中的 nums[i] > nums[j] 与归并过程比较时(合并两个有序数组)是一样的，但是这道题的比较是 nums[i] > 2 * nums[j]，与归并过程比较时不同。

解决方法就是：
要在归并过程之前计算翻转对的个数。因为我们要利用这两个数组有序的特性：
策略1：计算当前元素后面，有多少元素的两倍比我小，此时降序
此时让 cur1 和 cur2 指向两个区间的开始，盯着 cur1 的元素，先固定cur1不动：
(1) 若 nums[cur1] <= 2 * nums[cur2]，由于是降序数组，只有 cur2向后移时，才能让nums[cur1] > 2 * nums[cur2]
(2) cur2++，直到 nums[cur1] > 2 * nums[cur2] ，此时 ret += right - cur2 + 1
(3) 再让cur1++，注意此时 cur2 还是一直往后走
(4) 直到 cur1 或 cur2 走出区间
在这里插入图片描述
策略2：计算当前元素之前，有多少元素的一半比我大，此时升序
在这里插入图片描述

代码实现：

class Solution 
{int tmp[50010];
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;// [left, mid] [mid+1, right]int ret = 0;// 计算左右区间的个数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[cur2++] : nums[cur1++];// 处理剩下的数据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;}
};

策略1和策略2的代码差异：
策略1：降序

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

策略2：升序

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

三，算法总结

上面的若干道题都是基于快排和归并的思想解决的，所以最重要的还是要理解这两种排序算法。
如果想要更加详细的学习两种排序算法，请点击下面两篇文章：
(1) 归并排序和计数排序
(2) 快速排序和冒泡排序


http://www.ppmy.cn/news/1532042.html

相关文章

【网站架构部署与优化】nginx反向代理

【网站架构部署与优化】nginx反向代理

文章目录 nginx反向代理代理服务器正向代理与反向代理Nginx的负载均衡Nginx的动静分离 七层反向代理四层反向代理Nginx负载均衡调度策略1. 轮询&#xff08;Round-Robin, RR&#xff09;2. 加权轮询&#xff08;Weighted Round-Robin, WRR&#xff09;3. 最少连接&#xff08;L…
阅读更多...
OpenAPI鉴权（二）jwt鉴权

OpenAPI鉴权（二）jwt鉴权

一、思路 前端调用后端可以使用jwt鉴权&#xff1b;调用三方接口也可以使用jwt鉴权。对接多个三方则与每个third parth都约定一套token规则&#xff0c;因为如果使用同一套token&#xff0c;token串用可能造成权限越界问题&#xff0c;且payload交叉业务不够清晰。下面的demo包…
阅读更多...
英特尔®以太网网络适配器E810-CQDA1 / E810-CQDA2 网卡 规格书 e810 网卡 规格书 Intel100G E810 网卡 白皮书

英特尔®以太网网络适配器E810-CQDA1 / E810-CQDA2 网卡 规格书 e810 网卡 规格书 Intel100G E810 网卡 白皮书

英特尔以太网800系列网络适配器 英特尔以太网网络适配器E810-CQDA1 / CQDA2 在10到100Gbps的以太网速度下实现高效的工作负载优化性能 关键特性 •单、双端口QSFP28 •应用设备队列(ADQ) •PCI Express (PCIe) 4.0 x16 •动态设备个性化(DDP) •以太网端口配置工具(EPC…
阅读更多...
[Oracle] ORA-04036: 实例使用的 PGA 内存超出 PGA_AGGREGATE_LIMIT

[Oracle] ORA-04036: 实例使用的 PGA 内存超出 PGA_AGGREGATE_LIMIT

有说该问题是因为触发了Oracle的BUG导致&#xff0c;最直接的解决方法就是重启数据库实例&#xff1b; Linux下数据库实例重启
阅读更多...
3.5k star 一款开源简单好用的前端TAG标签组建库

3.5k star 一款开源简单好用的前端TAG标签组建库

今天我要给大家介绍一个在GitHub上备受好评的轻量级、高效的标签输入组件——Tagify。 一、Tagify简介 Tagify是一个用Vanilla JS、React、Angular和Vue编写的标签输入组件。它可以将普通的输入框或文本区域轻松转换为功能丰富的标签组件，具有出色的性能和小巧的代码体积。 …
阅读更多...
Spark JobHistory Server清理日志功能未生效,导致频繁挂掉

Spark JobHistory Server清理日志功能未生效,导致频繁挂掉

查看日志清理功能是打开的&#xff1a;spark.history.fs.cleaner.enabled true&#xff0c; spark.history.fs.cleaner.interval 和spark.history.fs.cleaner.maxAge使用的是默认值。 但是/user/spark/applicationHistory/ 目录下日志一直未不清理&#xff01;存储的日志数量超…
阅读更多...
报数游戏 - 华为OD统一考试(E卷)

报数游戏 - 华为OD统一考试(E卷)

2024华为OD机试&#xff08;E卷D卷C卷&#xff09;最新题库【超值优惠】Java/Python/C合集 题目描述 100个人围成一圈&#xff0c;每个人有一个编号&#xff0c;编号从1开始到100。他们从1开始依次报数&#xff0c;报到为M的人自动退出圈圈&#xff0c;然后下一个人接着从1开始…
阅读更多...
基于RustDesk自建远程桌面服务

基于RustDesk自建远程桌面服务

最近向日葵越来越难用了&#xff0c;官方好像限制了免费用户的带宽&#xff0c;但是限制的有点过头了&#xff0c;卡的基本没法用。 向日葵的平替todesk对于免费用户又有时长限制&#xff0c;对于经常用的小伙伴不大友好。 咱也不是说非得白嫖&#xff0c;但是向日葵和todesk这…
阅读更多...
最新文章

Copyright @ 2022~2023