資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律C++ 中求最大元素大於 k 的子陣列個數
給定一個包含整數元素的陣列 arr[] 和一個變數 k。目標是找到 arr[] 的子陣列中最大元素大於 k 的個數。如果陣列為 [1,2,3]，k 為 1。那麼可能的子陣列為 [1]，[2]，[3]，[1,2]，[2,3]，[1,2,3]。最大元素大於 1 的子陣列為 [2]，[3]，[1,2]，[2,3]，[1,2,3]。所以個數為 5。
讓我們透過示例來理解
輸入 − arr[] = {1,2,5,3 } k=3
輸出 − 最大元素大於 k 的子陣列個數為 − 6
解釋 − 所有可能的子陣列為 [1]，[2]，[5]，[3]，[1,2]，[2,5]，[5,3]，[1,2,5]，[2,5,3]，[1,2,5,3]。其中最大元素大於 3 的子陣列是包含 5 的那些子陣列。它們是 −
[5], [2,5], [5,3], [1,2,5], [2,5,3], [1,2,5,3].
總共 6 個子陣列。
輸入 − arr[] = {1,2,3,4,5 } k=4
輸出− 最大元素大於 k 的子陣列個數為 − 5
解釋 − 唯一大於 4 的元素是 5。包含 5 的子陣列將是 −
[5], [4,5], [3,4,5], [2,3,4,5], [1,2,3,4,5].
總共 5 個子陣列。
下面程式中使用的演算法如下
在這種方法中，我們知道具有 n 個元素的陣列的子陣列總數為 n*(n+1)/2。
我們現在將查詢元素小於 k 的子陣列。為此，我們跳過大於 k 的元素，並計算所有元素都小於 k 的子陣列的長度。對於每個長度 l，每個子陣列可以構成 l*(l+1)/2 個子陣列。將此值新增到每個此類子陣列中，稱為 X。最後，我們從 n*(n+1)/2 中減去此值 X 以獲得所需的結果。
將整數陣列 arr[] 和變數 k 作為輸入。
函式 maximum_k(int arr[], int size, int k) 獲取陣列、k 和陣列的長度，並返回最大元素大於 k 的子陣列的個數
將初始計數設定為 0。
使用 while 迴圈，遍歷從索引 i=0 到 i<size 的陣列。
對於每個元素，如果 arr[i]>k，則使用 continue 語句跳過它。
否則，使用內部 while 迴圈開始計算子陣列的長度。
如果 arr[i]<k 且 i<size。遞增 i 和 temp（所有元素都小於 k 的子陣列的長度）。
在內部 while 迴圈結束時，我們將 temp 作為當前子陣列的長度。
計算 temp*(temp+1)/2 並新增到計數中。
對所有此類子陣列執行此操作。
在外部 while 迴圈結束時。我們有變數 count 作為所有元素都小於 k 的子陣列的個數。
透過從 arr[] 的所有可能的子陣列個數（即 size*(size-1)/2）中減去此計數來更新計數。
返回 count 作為結果。
示例
#include <bits/stdc++.h>
using namespace std;
int maximum_k(int arr[], int size, int k){
int count = 0;
int i = 0;
while (i < size){
if (arr[i] > k){
i++;
continue;
}
int temp = 0;
while (i < size && arr[i] <= k){
i++;
temp++;
}
int temp_2 = temp * (temp + 1);
count = count + temp_2 / 2;
}
count = (size * (size + 1) / 2 - count);
return count;
}
int main(){
int arr[] = { 4, 1, 2, 7, 8, 3 };
int k = 5;
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of subarrays whose maximum element is greater than k are: "<<maximum_k(arr, size, k);
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出 −
Count of subarrays whose maximum element is greater than k are: 14
273 次瀏覽
