专业做国际网站的公司,做一款网站注意啥,宝塔没有域名直接做网站怎么弄,山东莱芜金点子电子版系列专栏
双指针
模拟算法
分治思想 目录
1、题目链接
2、题目介绍
3、解法
4、代码 1、题目链接
LCR 159. 库存管理 III - 力扣#xff08;LeetCode#xff09;
2、题目介绍 在股票交易中#xff0c;如果前一天的股价高于后一天的股价#xff0c;则可以认为存在一…系列专栏
双指针
模拟算法
分治思想 目录
1、题目链接
2、题目介绍
3、解法
4、代码 1、题目链接
LCR 159. 库存管理 III - 力扣LeetCode
2、题目介绍 在股票交易中如果前一天的股价高于后一天的股价则可以认为存在一个「交易逆序对」。请设计一个程序输入一段时间内的股票交易记录 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 3、解法 逆序对的计算 在归并排序的合并步骤中当我们将两个已排序的子数组合并成一个有序数组时如果左侧子数组中的某个元素大于右侧子数组中的某个元素那么左侧子数组中该元素之后的所有元素包括该元素本身都将与右侧子数组中的该元素形成逆序对。因此我们可以通过计算这样的元素对数来统计逆序对的总数。 具体实现 分割将数组分成左右两部分递归地对它们进行排序。合并与计数在合并过程中使用两个指针分别指向左右子数组的起始位置比较两个指针所指向的元素。如果左侧元素大于右侧元素则左侧元素及其之后的所有元素都将与右侧当前元素形成逆序对因此逆序对数增加 mid - cur1 1mid 是左右子数组的分界点cur1 是左侧子数组的当前指针位置。然后将较小的元素放入临时数组 tmp 中并移动相应的指针。复原将临时数组 tmp 中的元素复制回原数组 record以完成排序和逆序对的计算。时间复杂度归并排序的时间复杂度为 O(n log n)其中 n 是数组的长度。在合并过程中我们遍历了每个元素一次因此计算逆序对的额外时间复杂度也是 O(n log n)。空间复杂度归并排序需要额外的空间来存储临时数组 tmp其大小为 n因此空间复杂度为 O(n)。 4、代码
//归并排序
//升序
class Solution {vectorint tmp;
public:int reversePairs(vectorint record) {tmp.resize(record.size());return mergeSort(record, 0, record.size() - 1);}// 查找区间内的逆序对总数归并排序思想int mergeSort(vectorint record, int left, int right){if (left right) return 0;// 1. 找中点将数组分成两部分// [left,mid] [mid1,right]int mid (right - left) / 2 left;int ret 0;// 2. 左边的个数 排序 ,右边的个数 排序ret mergeSort(record, left, mid);ret mergeSort(record, mid 1, right);// 3. 一左一右的个数升序版本int cur1 left, cur2 mid 1, i 0;while (cur1 mid cur2 right){if (record[cur1] record[cur2]) tmp[i] record[cur1];else{ret mid - cur1 1;//合并过程中计数逆序对tmp[i] record[cur2];}}// 4. 处理排序过程while (cur1 mid) tmp[i] record[cur1];while (cur2 right) tmp[i] record[cur2];// 复原for (int i left; i right; i)record[i] tmp[i - left];return ret;}
}; 感谢阅读
