資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中統計元素小於等於 X 的子陣列數量
給定一個包含整數的陣列 arr[] 和一個變數 X。目標是統計 arr[] 的所有子陣列，使得每個子陣列僅包含小於或等於 X 的元素。例如，如果陣列為 [1,2,3] 且 X=2，則子陣列將為 [1]、[2] 和 [1,2]
讓我們透過示例來理解。
輸入 − arr[] = { 4,3,2,1,6 }; X=3
輸出 − 元素小於或等於 X 的子陣列數量為 − 6
說明 − 子陣列將為 −
[3], [2], [1], [3,2], [2,1], [3,2,1]
輸入 − arr[] = { 3,6,2,7,1,8,5 }; X=5
輸出 − 元素小於或等於 X 的子陣列數量為 − 4
說明 − 子陣列將為 −
[3], [2], [1], [5]
下面程式中使用的方案如下
我們正在建立一個與原始陣列 arr[] 大小相同的二進位制陣列 temp_arr[]。如果相應的 arr[i] 小於或等於 X，則此二進位制陣列將為 1，否則為 0。現在遍歷 temp_arr[] 並檢查連續的 1（arr[] 中小於 X 的元素）。將每個此類子陣列的長度儲存在 temp 中。對於長度為 temp 的陣列。子陣列總數將為 temp*(temp+1)/2。將其新增到總計數中，並繼續到 temp_arr[] 的末尾。
獲取陣列 arr[] 和變數 X。
函式 sub_X(int arr[], int size, int x) 獲取陣列和 x 並返回僅包含小於或等於 x 的元素的子陣列的數量。
獲取臨時變數 temp 和此類子陣列的最終總數作為 count。
獲取長度與 arr[] 相同的二進位制陣列 temp_arr[]。
我們將使用 for 迴圈從 i=0 到 i<size 遍歷陣列 arr[]。
對於每個元素 arr[i]<=x，將 temp_arr[i] 設定為 1，否則為 0。
使用 for 迴圈遍歷 temp_arr[]。
如果任何元素 temp_arr[i] == 1。然後使用從當前索引 i 到 temp_arr[temp_2]（temp_2=i+1；temp_2<size）為 1 的子迴圈進行遍歷。如果為 0，則中斷子迴圈。
所有 1 的子陣列的計數將為 temp= temp_2-i。
此子陣列包含所有 1，這意味著 arr[i] 中的所有元素都 <= x。子陣列總數將為 temp_3= temp*(temp+1)/2。
在兩次遍歷結束時，count 將包含 arr 中所有子陣列的總數，這些子陣列的數字小於或等於 x。
示例
#include <iostream>
using namespace std;
int sub_X(int arr[], int size, int x){
int count = 0, temp = 0;
int temp_arr[size];
for (int i = 0; i < size; i++){
if (arr[i] <= x){
temp_arr[i] = 1;
}
else{
temp_arr[i] = 0;
}
}
for (int i = 0; i < size; i++){
if (temp_arr[i] == 1){
int temp_2;
for(temp_2 = i + 1; temp_2 < size; temp_2++){
if(temp_arr[temp_2] != 1){
break;
}
}
temp = temp_2 - i;
int temp_3 = (temp) * (temp + 1)/2;
count = count + temp_3;
i = temp_2;
}
}
return count;
}
int main(){
int arr[] = { 2, 6, 1, 10, 5, 3 };
int x = 4;
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of sub-arrays which have elements less than or equal to X are: "<<sub_X(arr, size, x);
return 0;
}輸出
如果我們執行上述程式碼，它將生成以下輸出：
Count of sub-arrays which have elements less than or equal to X are: 3
251 次瀏覽
