济南专业网站优化,花西子的网络营销策略,巩义自助建站优化,备份wordpress到百度云算法沉淀——分治算法 快排思想01.颜色分类02.排序数组03.数组中的第K个最大元素04.库存管理 III 归并思想01.排序数组02.交易逆序对的总数03.计算右侧小于当前元素的个数04.翻转对 分治算法是一种解决问题的算法范式#xff0c;其核心思想是将一个大问题分解成若干个小问题其核心思想是将一个大问题分解成若干个小问题递归地解决这些小问题最后将它们的解合并起来得到原问题的解。分治算法的一般步骤包括分解Divide、解决Conquer、合并Combine。 具体来说分治算法包含以下几个步骤
分解Divide 将原问题分解成若干个规模较小、相互独立的子问题。这一步通常是问题规模的减小或者数据规模的缩小。解决Conquer 递归地解决这些子问题。对于规模较小的子问题可以直接求解。合并Combine 将子问题的解合并起来得到原问题的解。
分治算法通常适用于能够被划分成相互独立子问题的问题并且这些子问题的结构和原问题一样。经典的分治算法有许多如归并排序、快速排序、二分搜索等。
经典例子归并排序
分解Divide 将待排序的数组分成两半。解决Conquer 对每个子数组进行归并排序递归地进行排序。合并Combine 合并已排序的子数组得到最终的排序结果。
分治算法的优点包括
模块化设计 将问题分解成小问题使得算法结构清晰易于理解和实现。可并行性 分治算法通常适用于并行计算因为子问题可以独立地求解。适用范围广 适用于一类问题如排序、查找等。
快排思想
01.颜色分类
题目链接https://leetcode.cn/problems/sort-colors/
给定一个包含红色、白色和蓝色、共 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.length1 n 300nums[i] 为 0、1 或 2
思路
具体的思路可以分为以下三个部分
红色部分0 通过交换保证红色元素的右边界 left 的左侧都是红色元素。初始时left 设置为-1。白色部分1 遍历过程中遇到白色元素1时直接将指针 i 向右移动不进行交换。白色元素已经排列在红色元素的右侧所以不需要额外操作。蓝色部分2 通过交换保证蓝色元素的左边界 right 的右侧都是蓝色元素。初始时right 设置为数组的长度。
整个过程在遍历指针 i 小于右边界 right 的情况下进行。当 i 与 right 相遇时排序完成。
代码
class Solution {
public:void sortColors(vectorint nums) {for(int i0,left-1,rightnums.size();iright;){if(nums[i]0) swap(nums[left],nums[i]);else if(nums[i]1) i;else swap(nums[i],nums[--right]);}}
};02.排序数组
题目链接https://leetcode.cn/problems/sort-an-array/
给你一个整数数组 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 * 104-5 * 104 nums[i] 5 * 104
思路
普通快排在这里是通过不了的所以我们可以使用上面颜色分类的思想进行三路划分的优化
三路划分是对传统快速排序算法的一种改进通过将数组划分为三个部分小于、等于、大于基准值从而在存在大量相同元素的情况下提高了性能。
传统快速排序在处理有大量相同元素的数组时可能会导致不均匀的划分使得递归树不平衡进而影响性能。三路划分通过在划分过程中将数组分为小于、等于、大于基准值的三个部分有效地解决了这一问题具有以下优势
减少重复元素的递归处理 在存在大量相同元素的情况下传统快速排序可能导致递归深度较大而三路划分能够将相同元素聚集在一起从而减少递归深度。避免不必要的交换 在传统快速排序中可能会进行多次相同元素的交换而三路划分通过将相同元素聚集在一起避免了不必要的交换操作提高了性能。适用于含有大量重复元素的场景 当数组中存在大量相同元素时三路划分能够更好地利用重复元素的信息提高排序效率。
三路划分的核心思想是通过一个循环将数组划分为小于、等于、大于基准值的三个部分。这样相同元素被聚集在等于基准值的部分从而在递归过程中能够更高效地处理重复元素。这一优化使得算法在处理包含大量相同元素的数组时性能更为稳定。
代码
class Solution {
public:int getRandom(vectorint nums,int left, int right){return nums[rand()%(right-left1)left];}void qsort(vectorint nums,int l, int r){if(lr) return;int keygetRandom(nums,l,r);int il,leftl-1,rightr1;while(iright){if(nums[i]key) swap(nums[left],nums[i]);else if(nums[i]key) i;else swap(nums[--right],nums[i]);}qsort(nums,l,left);qsort(nums,right,r);}vectorint sortArray(vectorint nums) {srand(time(NULL));qsort(nums,0,nums.size()-1);return nums;}
};03.数组中的第K个最大元素
题目链接https://leetcode.cn/problems/kth-largest-element-in-an-array/
给定整数数组 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 105-104 nums[i] 104
思路
这里最常规的写法应该是使用堆排但是这样达不到O(n)的时间复杂度所以这里我们结合快排中的三路划分思想
代码
class Solution {
public:int findKthLargest(vectorint nums, int k) {srand(time(NULL)); // 设置随机数种子return qsort(nums, 0, nums.size() - 1, k);}int qsort(vectorint nums, int l, int r, int k) {if (l r) return nums[l];// 1. 随机选择基准元素int key getRandom(nums, l, r);// 2. 根据基准元素将数组分为三块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]);}}// 3. 分情况讨论int c r - right 1, b right - left - 1;if (c k) {// 第 k 大元素在右侧部分return qsort(nums, right, r, k);} else if (b c k) {// 第 k 大元素等于基准元素return key;} else {// 第 k 大元素在左侧部分return qsort(nums, l, left, k - b - c);}}int getRandom(vectorint nums, int left, int right) {return nums[rand() % (right - left 1) left];}
};计算左、右和基准三个部分的元素个数 c 表示右侧部分元素的个数即大于基准元素的个数。b 表示基准元素左侧部分元素的个数即等于基准元素的个数。 判断第 k 大元素的位置 如果右侧部分元素个数 c 大于等于 k说明第 k 大元素在右侧部分。因此递归地在右侧部分中继续寻找第 k 大元素。如果 b c 大于等于 k说明第 k 大元素等于基准元素。此时基准元素即为所求的第 k 大元素直接返回基准元素的值。如果以上两个条件都不满足说明第 k 大元素在左侧部分。因此递归地在左侧部分中继续寻找第 k 大元素同时将 k 减去右侧和基准元素的个数。
这样的划分和递归过程保证了在不同情况下都能正确地找到第 k 大元素从而完成整个算法。这是随机化快速排序在选择第 k 大元素时的一种处理策略通过考虑基准元素左右两侧的元素个数提高了算法在寻找第 k 大元素时的效率。
04.库存管理 III
题目链接https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/
仓库管理员以数组 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
思路
这一题和上一题的思路基本一致同样我们使用快速选择的算法可以使时间复杂度达到O(n)只不过需要简单做一些调整
代码
class Solution {
public:void qsort(vectorint nums, int l, int r, int k) {if (l r) return;// 随机选择基准元素int key nums[rand() % (r - l 1) l];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 a left - l 1, b right - left - 1;// 根据划分情况递归处理if (a k) {// 第 k 小元素在左侧部分qsort(nums, l, left, k);} else if (a b k) {// 第 k 小元素在基准元素右侧且可能包含部分基准元素return;} else {// 第 k 小元素在右侧部分qsort(nums, right, r, k - a - b);}}vectorint inventoryManagement(vectorint stock, int cnt) {srand(time(NULL));// 调用随机化快速排序qsort(stock, 0, stock.size() - 1, cnt);// 返回前 cnt 小的商品return {stock.begin(), stock.begin() cnt};}
};归并思想
01.排序数组
题目链接https://leetcode.cn/problems/sort-an-array/
给你一个整数数组 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 * 104-5 * 104 nums[i] 5 * 104
思路
要理解分治中的归并思想首先我们从归并排序入手这里我直接编写代码想看更清晰的排序剖析可以翻看博主之前关于八大排序的博客
代码
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 (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];}
};02.交易逆序对的总数
题目链接https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
在股票交易中如果前一天的股价高于后一天的股价则可以认为存在一个「交易逆序对」。请设计一个程序输入一段时间内的股票交易记录 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思路
这里我们使用归并的思想可以对数组边排序边进行逆序对的计算我们在进行归并排序划分时左边和右边都是相对有序的我们在归并时找到了左边相对右边大的那个数就可以进行一次逆序对的组合即此时左边被遍历的数及其之后的数都能和此时右边的数进行逆序匹配此时我们累加逆序对的值直到我们把整个数组归并完毕逆序对的总数也就计算完毕了
代码
class Solution {int tmp[50000];
public:int reversePairs(vectorint record) {return mergeSort(record, 0, record.size() - 1);}int mergeSort(vectorint 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 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;}
};03.计算右侧小于当前元素的个数
题目链接https://leetcode.cn/problems/count-of-smaller-numbers-after-self/
给你一个整数数组 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 105-104 nums[i] 104
思路
我们可以继续利用上面的逆序对思想只不过我们需要使用额外的数组来记录相对下标。
代码
class Solution {vectorint ret;vectorint index;int tmp[500000];int tindex[500000];
public:vectorint countSmaller(vectorint nums) {int nnums.size();ret.resize(n);index.resize(n);for(int i0;in;i) index[i]i;mergeSort(nums,0,n-1);return ret;}void mergeSort(vectorint nums,int left,int right){if(leftright) return;int mid(leftright)1;mergeSort(nums,left,mid);mergeSort(nums,mid1,right);int cur1left,cur2mid1,i0;while(cur1midcur2right){if(nums[cur1]nums[cur2]){tmp[i]nums[cur2];tindex[i]index[cur2];}else{ret[index[cur1]]right-cur21;tmp[i]nums[cur1];tindex[i]index[cur1];}}while(cur1mid){tmp[i]nums[cur1];tindex[i]index[cur1];}while(cur2right){tmp[i]nums[cur2];tindex[i]index[cur2];}for(int jleft;jright;j){nums[j]tmp[j-left];index[j]tindex[j-left];}}
};04.翻转对
题目链接https://leetcode.cn/problems/reverse-pairs/
给定一个数组 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位整数的表示范围内。
思路
总体思路依旧是使用归并我们在每次排序前找到当前的左边某个数大于右边的两倍即可一次性计算该数后面的翻转对个数数组排序完成即可计算全部的翻转对
代码
class Solution {int tmp[50000];
public:int reversePairs(vectorint nums) {return mergeSort(nums,0,nums.size()-1);}int mergeSort(vectorint nums,int left,int right){if(leftright) return 0;int ret0;int mid(leftright)1;retmergeSort(nums,left,mid);retmergeSort(nums,mid1,right);int cur1left,cur2mid1,ileft;while(cur1mid){while(cur2rightnums[cur2]nums[cur1]/2.0) cur2;if(cur2right) break;retright-cur21;cur1;}cur1left,cur2mid1;while(cur1midcur2right) tmp[i]nums[cur1]nums[cur2]?nums[cur2]:nums[cur1];while(cur1mid) tmp[i]nums[cur1];while(cur2right) tmp[i]nums[cur2];for(int jleft;jright;j)nums[j]tmp[j];return ret;}
};
