大型网站开发团队的美工需要什么工作经验和教育背景及薪酬,wordpress下不了插件,seo的优点和缺点,网站建设丿金手指谷哥12文章目录 算法笔记#xff08;五#xff09;——分治快排颜色分类排序数组数组中的第K个最大元素库存管理 III 归并排序数组交易逆序对的总数计算右侧小于当前元素的个数翻转对 算法笔记#xff08;五#xff09;——分治 分治算法字面上的解释是“分而治之”#xff0c;就… 文章目录 算法笔记五——分治快排颜色分类排序数组数组中的第K个最大元素库存管理 III 归并排序数组交易逆序对的总数计算右侧小于当前元素的个数翻转对 算法笔记五——分治 分治算法字面上的解释是“分而治之”就是把一个复杂的问题分成两个或更多的相同或相似的子问题再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础如排序算法(快速排序归并排序)… 分治策略是对于一个规模为n的问题若该问题可以容易地解决比如说规模n较小则直接解决否则将其分解为k个规模较小的子问题这些子问题互相独立且与原问题形式相同递归地解这些子问题然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 步骤
分解将原问题分解为若干个规模较小相互独立与原问题形式相同的子问题解决若子问题规模较小而容易被解决则直接解否则递归地解各个子问题合并将各个子问题的解合并为原问题的解
经典的分治算法有二分搜索归并排序快速排序。
快排
颜色分类 题目颜色分类 思路
初始化三个指针i遍历数组left左侧均为0right右侧均为2遍历过程中遇到0swap(nums[left],nums[i])遇到1i不进行交换遇到2swap(nums[--right], nums[i])循环条件i right
C代码
class Solution
{
public:void sortColors(vectorint nums) {for(int i 0, left -1, right nums.size(); i right; ){if(nums[i] 0) swap(nums[left], nums[i]);else if(nums[i] 1)i;elseswap(nums[--right], nums[i]);}}
};排序数组 题目排序数组 思路
我们将数组划分为三块再来实现快排将数组划分为三个部分小于、等于、大于基准值keykeykey 三路划分减少重复元素的递归处理相同元素过多的话可以减小递归深度、避免不必要的交换将相同元素聚集在一起避免了不必要的交换操作 C代码
class Solution
{
public:int getKey(vectorint nums, int left, int right){return nums[rand() % (right - left 1) left];}void qsort(vectorint nums, int l, int r){if(l r) return;int key getKey(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]);}qsort(nums, l, left);qsort(nums, right, r);}vectorint sortArray(vectorint nums) {srand(time(NULL));qsort(nums, 0, nums.size() - 1);return nums;}
};数组中的第K个最大元素 题目数组中的第K个最大元素 思路 常规解法利用堆排但时间复杂度不为O(N) 快速选择算法快排O(N)
三路划分将数组划分为三块大于key的元素个数为c等于key的元素个数为b小于key元素个数为a若 c k则第k大元素在右侧继续在右侧递归寻找第k大元素若b c k则直接返回基准元素即为第k大元素若上述均不满足则第k大元素在左侧继续在左侧递归寻找第k大元素此时k k - b - c
C代码
class Solution
{
public:// 数组中获得随机值 int getKey(vectorint nums, int l, int r) {return nums[rand() % (r - l 1) l];}int qsort(vectorint nums, int l, int r, int k){if(l r) return nums[l];// 随机选择基准元素int key getKey(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]);}int b right - 1 - (left 1) 1; // 等于key的数量int c r - right 1; // 大于key的数量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 findKthLargest(vectorint nums, int k) {srand(time(NULL));return qsort(nums, 0, nums.size() - 1, k);}
};库存管理 III 题目库存管理 III 思路 和上题想法一致使用快速选择的算法使时间复杂度达到O(n) C代码 class Solution
{
public:void qsort(vectorint nums, int l, int r, int cnt){if(l r) return ;int key nums[rand() % (r - l 1) l];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]);}int a left - l 1;int b right - 1 - (left 1) 1;if(a cnt) qsort(nums, l, left, cnt);else if((a b) cnt) return;else qsort(nums, right, r, cnt - a - b);}vectorint inventoryManagement(vectorint stock, int cnt) {srand(time(NULL));qsort(stock, 0, stock.size() - 1, cnt);return {stock.begin(), stock.begin() cnt};}
};归并
排序数组 题目排序数组 C代码
class Solution
{// 归并vectorint tmp;
public:void mergeSort(vectorint nums, int l, int r){if(l r) return ;// 计算中间位置int mid (l r) 1;// 对左右两部分进行归并排序mergeSort(nums, l, mid);mergeSort(nums, mid 1, r);// 归并合并两个有序部分int i l, j mid 1, k 0;while(i mid j r)tmp[k] (nums[i] nums[j]) ? nums[i] : nums[j];while(i mid) tmp[k] nums[i];while(j r) tmp[k] nums[j];// 拷贝回原数组for(int i l; i r; i){nums[i] tmp[i - l];}} vectorint sortArray(vectorint nums) {tmp.resize(nums.size());mergeSort(nums, 0, (int)nums.size() - 1);return nums;}
};交易逆序对的总数 题目交易逆序对的总数 思路 当我们将两个已排序的子数组合并成一个有序数组时如果左侧子数组中的某个元素大于右侧子数组中的某个元素那么左侧子数组中该元素之后的所有元素包括该元素本身都将与右侧子数组中的该元素形成逆序对。因此我们可以通过计算这样的元素对数来统计逆序对的总数
C代码
class Solution
{int tmp[50010];
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;// [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 i left; i right; i)nums[i] tmp[i - left];return ret;}
};计算右侧小于当前元素的个数 题目计算右侧小于当前元素的个数 思路 这⼀道题的解法与求数组中的逆序对的解法是类似的记录每⼀个元素的右边有多少个元素⽐⾃⼰⼩ 归并排序的过程中元素的下标是会跟着变化的因此我们需要⼀个辅助数组来将数组元素和对应的下标绑定在⼀起归并也就是再归并元素的时候顺势将下标也转移到对应的位置上 C代码
class Solution
{vectorint ret;vectorint index; // 记录当前元素的元素下标int tmpNums[500010];int tmpIndex[500010];
public:vectorint countSmaller(vectorint nums) {int n nums.size();ret.resize(n); index.resize(n);// 初始化tmpIndexfor(int i 0; i n; i) index[i] i; mergeSort(nums, 0, n - 1);return ret;}void mergeSort(vectorint 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];}}
};翻转对 题目翻转对 思路 翻转对和逆序对的定义⼤同⼩异逆序对是前⾯的数要⼤于后⾯的数。⽽翻转对是前⾯的⼀个数要⼤于后⾯某个数的两倍。因此我们依旧可以⽤归并排序的思想来解决这个问题 C代码
class Solution
{int tmp[50010];
public:int reversePairs(vectorint nums) {return mergeSort(nums, 0, nums.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 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;}
};
