資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中統計所有元素都大於 K 的子陣列
給定一個整數陣列 arr[] 和一個數字 K。目標是統計 arr[] 的所有子陣列，使得子陣列的所有元素都大於 K 或 K 小於子陣列的所有元素。如果陣列為 [1,2,3] 且 K 為 1。子陣列將為 [2]、[3]、[2,3]。
讓我們透過示例來理解。
輸入 − arr[] = { 2, 2, 1, 1, 1, 5 }; K=1
輸出 − 所有元素都大於 K 的子陣列的數量為 − 4
解釋 − 子陣列將為：[2]、[2]、[5]、[2,2]。每個子陣列中的所有元素都大於 1。
輸入 − arr[] = { 3,4,5,6 }; K=2
輸出 − 所有元素都大於 K 的子陣列的數量為 − 10
解釋 − 子陣列將為 − [3]、[4]、[5]、[6]、[3,4]、[4,5]、[5,6]、[3,4,5]、[4,5,6]、[3,4,5,6]。總數=10。
下面程式中使用的方案如下
我們將使用 for 迴圈遍歷陣列。如果當前元素大於 K。則遞增計數。否則將計數設定為 0，並將總計設定為 count*(count+1)/2。（用於子陣列）。如果最後計數非零。則為剩餘子陣列的計數新增 count*(count+1)/2。
獲取一個數字陣列 arr[]。
函式 sub_greater_k(int arr[], int size, int k) 獲取陣列並返回所有元素都大於 k 的子陣列的數量。
將初始計數設定為 0。
我們將使用 for 迴圈從 i=0 到 i<size 遍歷陣列。
如果 arr[i]>k 則遞增計數。
具有計數（元素 > k）的子陣列將為 count*(count+1)/2。將此新增到所有此類子陣列的總計中。
最後再次將 count*(count+1)/2 新增到總計中，如果計數非零。
將總計作為結果返回。
示例
#include <bits/stdc++.h>
using namespace std;
int sub_greater_k(int arr[], int size, int k){
int count = 0;
int total = 0;
for (int i = 0; i < size; i++){
if (arr[i] > k){
count++;
}
else{
total += (count) * (count + 1) / 2;
count = 0;
}
}
if(count){
total += (count) * (count + 1) / 2;
}
return total;
}
int main(){
int arr[] = {2, 4, 6, 1, 3, 7, 9 };
int size = sizeof(arr) / sizeof(arr[0]);
int k = 7;
cout<<"Count of subarrays with all elements greater than K are: "<<sub_greater_k(arr, size, k);
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出：
Count of subarrays with all elements greater than K are: 1
383 次檢視
