数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中统计优质子数组的数量
假设我们有一个整数数组nums和一个整数k。如果一个子数组中包含k个奇数，则称该子数组为优质子数组。我们需要找到优质子数组的数量。例如，如果数组是[1,1,2,1,1]，k = 3，则输出为2，因为子数组是[1,1,2,1]和[1,2,1,1]
为了解决这个问题，我们将遵循以下步骤：
- ans := 0, n := nums数组的大小
- left := 0, right := 0, count := 0
- 定义一个数组odd，用nums中所有奇数值填充它
- 如果odd数组的长度>= k，则
- 对于i从0到k-1，j从k-1到odd数组大小-1，i和j分别加1
- left := 如果i = 0，则odd[i] + 1，否则odd[i] – odd[i – 1]
- right := 如果odd数组大小-1 = j，则odd[j]，否则odd[j + 1] – odd[j]
- ans := ans + left * right
- 对于i从0到k-1，j从k-1到odd数组大小-1，i和j分别加1
- 返回ans
示例(C++)
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int ans = 0;
int n = nums.size();
int left = 0;
int right = 0;
int cnt = 0;
vector <int> odd;
for(int i = 0; i < n; i++){
if(nums[i] % 2 == 1)odd.push_back(i);
}
if(odd.size()>=k){
for(int i = 0, j = k-1; j < odd.size(); i++, j++){
int left = i==0?odd[i]+1: odd[i] - odd[i-1];
int right = j==odd.size()-1 ?n-odd[j] : odd[j+1] - odd[j];
ans += left * right;
}
}
return ans;
}
};
main(){
vector<int> v = {1,1,2,1,1};
Solution ob;
cout <<ob.numberOfSubarrays(v, 3);
}输入
[1,1,2,1,1] 3
输出
2
更新于：2020年4月30日
793 次浏览
广告