今日学习记录
1. 3739. 统计主要元素子数组数目 II
关键词：前缀和 归并 线段树
问题分析：
给一个数组和一个 num,在数组中找到满足条件的子数组数目,该条件为在子数组中 num 出现的次数要严格大于子数组长度的一半
核心思路: 在子数组中 num 出现的次数为数组长度一半,那么在一个子数组中,假设 num 为 1,其他都为-1,则这个数组总和大于 0,即满足条件,所以我们先使用前缀和得到数组 pre
前缀和
设pre = {0,-1,0,1,0},要找到总和大于0的子数组数量我们似乎要维护一个有序集合,在每次枚举时,要找到小于该数的所有左边的数量,所以本质上就是找到顺序对这个问题,我们可以使用归并排序和线段树解决
归并排序
使用归并排序的话,只要写过归并排序的模板就行了,我们在对数组进行排序的时候,就能找到所有小区间里的顺序对,然后累加到答案上就行了,实现不难 代码:
class Solution {
public:
long long countMajoritySubarrays(vector<int>& nums, int target) {
int n = nums.size();
vector<int> pre(n+1);
for(int i = 1;i<=n;i++)
if(nums[i-1]==target) pre[i] = pre[i-1]+1;
else pre[i] = pre[i-1]-1;
vector<int> temp(n+1);
long long cnt = 0;
auto merge = [&](this auto&&merge,int l,int r)->long long{
if(l>=r) return 0;
int mid = l+(r-l)/2;
cnt = merge(l,mid)+merge(mid+1,r);
int i = l,j = mid+1,k = l;
while(i<=mid&&j<=r){
if(pre[i]<pre[j]){
temp[k++] = pre[i++];
cnt += r-j+1;
}
else temp[k++] = pre[j++];
}
while(i<=mid) temp[k++] = pre[i++];
while(j<=r) temp[k++] = pre[j++];
for(int p = l;p<=r;p++) pre[p] = temp[p];
return cnt;
};
return merge(0,n);
}
};线段树
基于归并的分治思想,我们就是要维护分区,进行计算,那么对区间维护使用线段树就能解决,会板子就行 **最终代码：
学到的点：
- 归并
- 线段树
总和大于0的子数组数量经典问题- 如何找逆序对/顺序对