C++前缀和算法的应用：统计中位数为 K 的子数组-摩杜云开发者社区

本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频

题目

给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的不同整数组成。另给你一个正整数 k 。
统计并返回 nums 中的中位数等于 k 的非空子数组的数目。
注意：
数组的中位数是按递增顺序排列后位于中间的那个元素，如果数组长度为偶数，则中位数是位于中间靠左的那个元素。
例如，[2,3,1,4] 的中位数是 2 ，[8,4,3,5,1] 的中位数是 4 。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [3,2,1,4,5], k = 4
输出：3
解释：中位数等于 4 的子数组有：[4]、[4,5] 和 [1,4,5] 。
示例 2：
输入：nums = [2,3,1], k = 3
输出：1
解释：[3] 是唯一一个中位数等于 3 的子数组。
参数范围：
n == nums.length
1 <= n <= 105
1 <= nums[i], k <= n
nums 中的整数互不相同

分析

变量解释


vSum[i]	记录nums[0,i)中小于k的数量
mLeftOdd	left为奇数的：l - 2*vSum[l]
mLeftEven	left为偶数的：l - 2*vSum[l]
mLenOdd	长度为奇数的：l - 2*vSum[l]
mLenEven	长度为偶数的：l - 2*vSum[l]

奇偶性


left为奇数	r为奇数	长度为奇数
left为奇数	r为偶数	长度为偶数
left为偶数	r为奇数	长度为偶数
left为偶数	r为偶数	长度为奇数

原理

假定nums[kIndex]等于k，则包括k的子数组可以表示为：nums[left,right]，left的取值范围为(-1,kIndex]，right的取值范围为[kIndex,m_c)。


nums[l,r]的长度： r-l+1。
nums[l,r]中小于k的数量: vSum[r+1]-vSum[l]。
如果长度是奇数：（长度-1）/2== k的数量则符合要求 => r-l = 2*(vSum[r+1]-vSum[l])
如果长度是偶数：（长度-2）/2 == k的数量则符合要求 => r-l-1 = 2*(vSum[r+1]-vSum[l])
将l相关移到右边：r - 2vSum[r+1] = l - 2vSum[l]; r - 2vSum[r+1]-1 = l - 2vSum[l]

代码

核心代码

class Solution {
 public:
 int countSubarrays(vector& nums, const int k) {
 m_c = nums.size();
 vector vSum = { 0 };//Vsum[i]记录nums[0,i)中小于k的数量
 for (const auto& n : nums)
 {
 vSum.emplace_back(vSum.back() + (n < k));
 } 
 unordered_map<int, int> mLeftEven, mLeftOdd;
 int left = 0;
 for (; left < m_c; left++)
 {
 auto& m = (left & 1) ? mLeftOdd : mLeftEven;
 m[left - 2 * vSum[left]]++;
 if (k == nums[left])
 {
 break;
 }
 }
 int iRet = 0;
 for (int r = left; r < m_c; r++)
 {
 const int tmp = r - 2 * vSum[r + 1];
 auto& mLenOdd = (r & 1) ? mLeftOdd : mLeftEven;
 auto& mLenEven = (r & 1) ? mLeftEven : mLeftOdd;
 iRet += mLenOdd[tmp] + mLenEven[tmp - 1];
 std::cout << “r:” << r << " 奇数：" << mLenOdd.count(tmp) << " 偶数：" << mLenEven.count(tmp - 1) << std::endl;
 }
 return iRet;
 }
 int m_c;
 };

测试用例

template
 void Assert(const vector& v1, const vector& v2)
 {
 if (v1.size() != v2.size())
 {
 assert(false);
 return;
 }
 for (int i = 0; i < v1.size(); i++)
 {
 assert(v1[i] == v2[i]);
 }
 }template
 void Assert(const T& t1, const T& t2)
 {
 assert(t1 == t2);
 }int main()
 {
 Solution slu;
 vector nums;
 int res;
 nums = { 5,11,4,6,2,7,10,8,1,3,9,12 };
 res = slu.countSubarrays(nums, 6);
 Assert(22, res);
 nums = { 2,3,1 };
 res = slu.countSubarrays(nums, 3);
 Assert(1, res);
 nums = { 3,2,1,4,5 };
 res = slu.countSubarrays(nums, 4);
 Assert(3, res);//CConsole::Out(res);}

2023年4月版

class Solution {
 public:
 int countSubarrays(vector& nums, int k) {
 m_c = nums.size();
 //大于K的数减小于K
 std::unordered_map<int, int> mSubNum;
 mSubNum[0] = 1;
 int i = 0;
 int iGreate = 0, iLess = 0;
 for (; (i < m_c)&&( nums[i] != k ) ; i++)
 {
 iGreate += nums[i] > k;
 iLess += nums[i] < k;
 mSubNum[iGreate - iLess]++;
 }
 int iRet = 0;
 for (; i < m_c; i++)
 {
 iGreate += nums[i] > k;
 iLess += nums[i] < k;
 iRet += mSubNum[iGreate - iLess];
 iRet += mSubNum[iGreate - iLess-1];
 }
 return iRet;
 }
 int m_c;
 };

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境： VS2022 C++17

C++前缀和算法的应用：统计中位数为 K 的子数组_开发语言