gta房产网站建设中,wordpress 设置文章页,模版网站是什么意思,大鹏网络网站建设分治 - 快速排序 分治 - 快速排序1. 颜色分类2. 排序数组(快速排序)3. 数组中的第K个最大元素4. 库存管理Ⅲ5. 排序数组(归并排序)6. 交易逆序对的总数7. 计算右侧小于当前元素的个数8. 翻转对 分治 - 快速排序
1. 颜色分类
做题链接 - Leetcode -75.颜色分类
题目… 分治 - 快速排序 分治 - 快速排序1. 颜色分类2. 排序数组(快速排序)3. 数组中的第K个最大元素4. 库存管理Ⅲ5. 排序数组(归并排序)6. 交易逆序对的总数7. 计算右侧小于当前元素的个数8. 翻转对 分治 - 快速排序
1. 颜色分类
做题链接 - Leetcode -75.颜色分类
题目给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums 原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1 输入nums [2, 0, 2, 1, 1, 0] 输出[0, 0, 1, 1, 2, 2]
示例 2 输入nums [2, 0, 1] 输出[0, 1, 2]
提示 n nums.length 1 n 300 nums[i] 为 0、1 或 2
思路快排思想三指针法使数组分三块。类比数组分两块的算法思想这里是将数组分成三块那么我们可以再添加⼀个指针实现数组分三块。
设数组大小为 n 定义三个指针 left, cur, right :
left 用来标记 0(红色) 序列的末尾因此初始化为 -1 cur 用来扫描数组初始化为 0 right 用来标记 2(蓝色) 序列的起始位置因此初始化为 n 。
在 cur 往后扫描的过程中保证
[0, left] 内的元素都是 0(红色) [left 1, cur - 1] 内的元素都是 1(白色) [cur, right - 1] 内的元素是待定元素[right, n] 内的元素都是 2(蓝色) .
代码如下 class Solution {public:void sortColors(vectorint nums) {// 使用三指针将数组分为三块最终分为以下三个模块// [0, left] 表示 0(红色) 序列// [left 1, right - 1] 表示 1(白色) 序列// [right, numsSize - 1] 表示 2(蓝色) 序列。 int cur 0, left -1, right nums.size();while(cur right){if(nums[cur] 0) swap(nums[left], nums[cur]);else if(nums[cur] 1) cur;else swap(nums[--right], nums[cur]);}}};2. 排序数组(快速排序)
做题链接 - Leetcode -912.排序数组
题目给你一个整数数组 nums请你将该数组升序排列。
示例 1 输入nums [5, 2, 3, 1] 输出[1, 2, 3, 5]
示例 2 输入nums [5, 1, 1, 2, 0, 0] 输出[0, 0, 1, 1, 2, 5]
提示 1 nums.length 5 * 10^4 5 * 10^4 nums[i] 5 * 10^4
由于思路比较明显使用快速选择算法递归处理选取一个基准值 key 将数组分为三块下面直接看代码 class Solution {public:vectorint sortArray(vectorint nums) {// 种下一个随机数种子srand(time(nullptr));// 快速选择算法将数组划分为三个区间my_qsort(nums, 0, nums.size() - 1);return nums;}void my_qsort(vectorint 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[i], nums[--right]);else if(nums[i] key) i;else swap(nums[left], nums[i]);}// [l, left] [left 1, right - 1] [right, r]my_qsort(nums, l, left);my_qsort(nums, right, r);}// 获取数组中随机一个数// 让随机数 % 上区间大小然后加上区间的左边界int getRandom(vectorint nums, int left, int right){return nums[rand() % (right - left 1) left];}};3. 数组中的第K个最大元素
题目链接 - Leetcode -215.数组中的第K个最大元素
Leetcode -215.数组中的第K个最大元素
题目给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。 请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1: 输入: [3, 2, 1, 5, 6, 4] , k 2 输出 : 5
示例 2 : 输入 : [3, 2, 3, 1, 2, 4, 5, 5, 6] , k 4 输出 : 4
提示
1 k nums.length 10^510^4 nums[i] 10^4
思路是使用快排思想将数组分为三块然后分三种情况讨论具体思路参考代码解析
代码如下 class Solution {public:int findKthLargest(vectorint nums, int k){srand(time(nullptr));return FindMaxTopk(nums, 0, nums.size() - 1, k);}int FindMaxTopk(vectorint nums, int l, int r, int k){if (l r) return nums[l];// 根据 key 将数组分为三块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]);}// [l, left] [left 1, right - 1] [right, r]int part2 right - left - 1, part3 r - right 1;// 分情况讨论// 情况1、区间3的个数大于等于k那么目标值一定在区间3if (part3 k) return FindMaxTopk(nums, right, r, k);// 情况2、区间2区间3的个数大于等于k目标值一定在区间2即一定是 keyelse if (part2 part3 k) return key;// 情况3、如果不满足上面情况则目标值一定在区间1else return FindMaxTopk(nums, l, left, k - part2 - part3);}// 获取数组内的一个随机值int getRandom(vectorint nums, int left, int right){return nums[rand() % (right - left 1) left];}};4. 库存管理Ⅲ
题目链接 - Leetcode -LCR 159.库存管理Ⅲ
Leetcode -LCR 159.库存管理Ⅲ
题目仓库管理员以数组 stock 形式记录商品库存表其中 stock[i] 表示对应商品库存余量。 请返回库存余量最少的 cnt 个商品余量返回 顺序不限。
示例 1 输入stock [2, 5, 7, 4], cnt 1 输出[2]
示例 2 输入stock [0, 2, 3, 6], cnt 2 输出[0, 2] 或[2, 0]
提示 0 cnt stock.length 10000 0 stock[i] 10000
思路与上题思路类似在快排中当我们把数组「分成三块」之后 [l, left] [left 1, right - 1] [right, r] 我们可以通过计算每一个区间内元素的「个数」进而推断出最小的 k 个数在哪些区间里面。那么我们可以直接去「相应的区间」继续划分数组即可。
代码如下 class Solution {public:void my_qsort(vectorint arr, int l, int r, int k){if(l r) return;// 根据 key 值分区间int key getRandom(arr, l, r);int i l, left l - 1, right r 1;while(i right){if(arr[i] key) swap(arr[left], arr[i]);else if(arr[i] key) i;else swap(arr[--right], arr[i]);}// 根据元素个数分情况讨论// [l, left] [left 1][right - 1] [right, r]int part1 left - l 1, part2 right - left - 1;if(part1 k) my_qsort(arr, l, left, k);else if(part1 part2 k) return;else my_qsort(arr, right, r, k - part1 - part2);}// 选取基准值int getRandom(vectorint arr, int left, int right){return arr[rand() % (right - left 1) left];}vectorint inventoryManagement(vectorint stock, int cnt) {srand(time(nullptr));// 快速选择算法将数组分为三个区间选择基准值key比key小的元素全扔到左边my_qsort(stock, 0, stock.size() - 1, cnt);return vectorint(stock.begin(), stock.begin() cnt);}};5. 排序数组(归并排序)
题目链接 - Leetcode -912.排序数组(归并排序)
Leetcode -912.排序数组(归并排序)
题目给你一个整数数组 nums请你将该数组升序排列。
示例 1 输入nums [5, 2, 3, 1] 输出[1, 2, 3, 5]
示例 2 输入nums [5, 1, 1, 2, 0, 0] 输出[0, 0, 1, 1, 2, 5]
提示
1 nums.length 5 * 10^45 * 10^4 nums[i] 5 * 10^4
思路归并排序的流程充分的体现了「分而治之」的思想大体过程分为两步
分将数组一分为二为两部分一直分解到数组的长度为 1 使整个数组的排序过程被分为「左半部分排序」 「右半部分排序」治将两个较短的「有序数组合并成⼀个长的有序数组」一直合并到最初的长度
代码如下 class Solution{vectorint tmp;public:vectorint sortArray(vectorint nums){tmp.resize(nums.size());mergeSort(nums, 0, nums.size() - 1);return nums;}void mergeSort(vectorint nums, int left, int right){if (left right) return;int mid left (right - left) / 2;// [left, mid] [mid 1, right]mergeSort(nums, left, mid);mergeSort(nums, mid 1, right);// 合并两个区间// vectorint tmp(right - left 1); // 可以在全局定义提高效率int i 0, 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 i left; i right; i)nums[i] tmp[i - left];}};6. 交易逆序对的总数
题目链接 - Leetcode -LCR 170.交易逆序对的总数
Leetcode -LCR 170.交易逆序对的总数
题目在股票交易中如果前一天的股价高于后一天的股价则可以认为存在一个「交易逆序对」。请设计一个程序输入一段时间内的股票交易记录 record返回其中存在的「交易逆序对」总数。
示例 1: 输入record [9, 7, 5, 4, 6] 输出8 解释交易中的逆序对为(9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。
限制
0 record.length 50000
思路用归并排序求逆序数主要就是在归并排序的合并过程中统计出逆序对的数量也就是在合并两个有序序列的过程中能够快速求出逆序对的数量。
1. 为什么可以利用归并排序
如果我们将数组从中间划分成两个部分那么我们可以将逆序对产生的方式划分成三组
逆序对中两个元素全部从左数组中选择逆序对中两个元素全部从右数组中选择逆序对中两个元素一个选左数组另一个选右数组
根据排列组合的分类相加原理三种情况下产生的逆序对的总和正好等于总的逆序对数量。
而这个思路正好匹配归并排序的过程
先排序左数组再排序右数组左数组和右数组合⼆为一
因此我们可以利用归并排序的过程先求出左半数组中逆序对的数量再求出右半数组中逆序对的数量最后求出一个选择左边另一个选择右边情况下逆序对的数量三者相加即可。
2. 为什么要这么做
在归并排序合并的过程中我们得到的是两个有序的数组。我们是可以利用数组的有序性快速统计出逆序对的数量而不是将所有情况都枚举出来。
最核心的问题如何在合并两个有序数组的过程中统计出逆序对的数量合并两个有序序列时求逆序对的方法有两种
快速统计出某个数前面有多少个数比它大快速统计出某个数后面有多少个数比它小
代码如下 class Solution{vectorint tmp;public:int reversePairs(vectorint nums){tmp.resize(nums.size());return mergeSort(nums, 0, nums.size() - 1);}int mergeSort(vectorint nums, int left, int right){if (left right) return 0;// [left, mid] [mid 1, right]int mid left (right - left) / 2;// 先统计两个区间各自的逆序对个数 排序int ret 0;ret mergeSort(nums, left, mid);ret mergeSort(nums, mid 1, right);// 两个区间每个区间选一个进行比较因为比较时区间已经排序好所以当cur1中出现第一次比cur2大的数时cur1 后面的数都可以全部统计int cur1 left, cur2 mid 1, i 0;while (cur1 mid cur2 right){if (nums[cur1] nums[cur2]) ret mid - cur1 1;tmp[i] nums[cur1] nums[cur2] ? nums[cur1] : nums[cur2];}// 处理细节还没结束的指针后的数全放入tmp中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;}};7. 计算右侧小于当前元素的个数
题目链接 - Leetcode -315.计算右侧小于当前元素的个数
Leetcode -315.计算右侧小于当前元素的个数
题目给你一个整数数组 nums 按要求返回一个新数组 counts 。数组 counts 有该性质 counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例 1 输入nums [5, 2, 6, 1] 输出[2, 1, 1, 0] 解释 5 的右侧有 2 个更小的元素(2 和 1) 2 的右侧仅有 1 个更小的元素(1) 6 的右侧有 1 个更小的元素(1) 1 的右侧有 0 个更小的元素
示例 2 输入nums [-1] 输出[0]
示例 3 输入nums [-1, -1] 输出[0, 0]
提示
1 nums.length 10^510^4 nums[i] 10^4
思路这一道题的解法与上一题的解法是类似的但是这一道题要求的不是求总的个数而是要返回一个数组记录每一个元素的右边有多少个元素比自己小。
但是在我们归并排序的过程中元素的下标是会跟着变化的因此我们需要一个辅助数组来将数组元素和对应的下标绑定在一起归并也就是再归并元素的时候顺势将下标也转移到对应的位置上。
代码如下 class Solution {// 将原数组的元素和下标绑定在一起元素顺序改变时对应的下标也跟着改变vectorint tmpElement, tmpIndex;vectorint index;vectorint ret;public:vectorint countSmaller(vectorint nums) {ret.resize(nums.size());index.resize(nums.size());// 初始化下标for(int i 0; i nums.size(); i)index[i] i;tmpElement.resize(nums.size());tmpIndex.resize(nums.size());mergeSort(nums, 0, nums.size() - 1);return ret;}void mergeSort(vectorint nums, int left, int right){if(left right) return;int mid left (right - left) / 2;// [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){// index[cur1] 存的是 nums[cur1] 这个元素的原始下标if(nums[cur1] nums[cur2]) ret[index[cur1]] right - cur2 1;// 同步更新下标和元素tmpIndex[i] nums[cur1] nums[cur2]? index[cur1] : index[cur2];tmpElement[i] nums[cur1] nums[cur2]? nums[cur1] : nums[cur2];}while(cur1 mid){tmpIndex[i] index[cur1];tmpElement[i] nums[cur1];}while(cur2 right){tmpIndex[i] index[cur2];tmpElement[i] nums[cur2];}// 同步拷贝下标和元素for(int j left; j right; j){index[j] tmpIndex[j - left];nums[j] tmpElement[j - left];}}};8. 翻转对
题目链接 - Leetcode -493.翻转对
Leetcode -493.翻转对
题目给定一个数组 nums 如果 i j 且 nums[i] 2 * nums[j] 我们就将(i, j) 称作一个重要翻转对。 你需要返回给定数组中的重要翻转对的数量。
示例 1 输入: [1, 3, 2, 3, 1] 输出 : 2
示例 2 : 输入 : [2, 4, 3, 5, 1] 输出 : 3
注意 : 给定数组的长度不会超过50000。 输入数组中的所有数字都在32位整数的表示范围内。
思路翻转对和逆序对的定义大同小异逆序对是前面的数要大于后面的数。而翻转对是前面的⼀个数要大于后面某个数的两倍。因此我们依旧可以用归并排序的思想来解决这个问题。
大思路与求逆序对的思路一样就是利用归并排序的思想将求整个数组的翻转对的数量转换成三部分左半区间翻转对的数量右半区间翻转对的数量一左一右选择时翻转对的数量。重点就是在合并区间过程中如何计算出翻转对的数量。
例如 left [4, 5, 6] right [3, 4, 5] 时如果是归并排序的话我们需要计算 left 数组中有多少个能与 3 组成翻转对。但是我们要遍历到最后⼀个元素 6 才能确定时间复杂度较高。因此我们需要在归并排序之前完成翻转对的统计。
下面以⼀个示例来模仿两个有序序列如何快速求出翻转对的过程假定已经有两个已经有序的序列 left [4, 5, 6] right [1, 2, 3] 用两个指针 cur1 和 cur2 遍历两个数组
对于任意给定的 left[cur1] 而言我们不断地向右移动 cur2直到 left[cur1] 2 * right[cur2]。此时对于 right 数组而言cur2 之前的元素全部都可以与 left[cur1] 构成翻转对。随后我们再将 cur1 向右移动⼀个单位此时 cur2 指针并不需要回退因为 left 数组是升序的依旧往右移动直到 left[cur1] 2 * right[cur2]。不断重复这样的过程就能够求出所有左右端点分别位于两个子数组的翻转对数目。
由于两个指针最后都是不回退的的扫描到数组的结尾因此两个有序序列求出翻转对的时间复杂度是 O(N).
综上所述我们可以利用归并排序的过程将求一个数组的翻转对转换成求左数组的翻转对数量 右数组中翻转对的数量 左右数组合并时翻转对的数量。
代码如下 class Solution {vectorint tmp;public:int reversePairs(vectorint nums) { tmp.resize(nums.size());return mergeSort(nums, 0, nums.size() - 1);}int mergeSort(vectorint nums, int left, int right){if(left right) return 0;// 1.根据中间元素划分区间int mid left (right - left) / 2;// 2. 先计算左右区间的翻转对// [left, mid] [mid 1, right]int ret 0;ret mergeSort(nums, left, mid);ret mergeSort(nums, mid 1, right);// 3.先利用左右区间有序的性质计算翻转对的数量int cur1 left, cur2 mid 1, i 0;while(cur1 mid){while(cur2 right nums[cur2] nums[cur1] / 2.0) cur2;ret right - cur2 1;cur1;}// 4.合并归并区间cur1 left, cur2 mid 1;while(cur1 mid cur2 right)tmp[i] nums[cur2] nums[cur1]? 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 - left];return ret;}};
