資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學使用 C++ 統計子陣列個數，要求子陣列元素的平均值大於陣列中其餘元素的平均值
給定一個包含正整數的陣列 arr[]。目標是找到 arr[] 的子陣列數量，這些子陣列的元素平均值大於不在其中的 arr[] 中其餘元素的平均值。
例如
輸入
arr[ ] = { 3, 2, 4 }輸出
Count of number of sub-arrays such that the average of elements present in the sub−array is greater than that do not present in the sub−array are: 2
解釋
The subarrays are − [ 3 ], [ 2 ], [ 4 ], [ 3,2 ], [ 2,4 ], [ 3,2,4 ]. Average of [ 4 ] is 4 which is more than the average of [ 2,3 ]. Average of [ 3,2,4 ] is 3 which is more than the average of [ ]
輸入
arr[ ] = { 3, 3, 3 }輸出
Count of number of sub−arrays such that the average of elements present in the sub−array is greater than that do not present in the sub−array are: 1
解釋
The subarrays are − [ 3 ], [ 3 ], [ 3 ], [ 3,3 ], [ 3,3 ], [ 3,3,3 ]. Average of [ 3,3,3 ] is 3 which is more than the average of [ ]
以下程式中使用的演算法如下 −
在這個演算法中，建立一個字首和陣列，它將把元素的和儲存到索引 i 的 new_arr[i] 中。現在我們有了直到前一個元素的和，然後計算直到 arr[i] 的和以及元素數量為 j−i+1，並計算平均值。
將陣列 arr[] 作為輸入。
函式 count(int arr[], int size) 獲取 arr[] 並返回子陣列的數量，這樣子陣列中元素的平均值就大於不在子陣列中的元素的平均值。
獲取一個數組 new_arr[size] 來儲存直到前一個索引元素的和。
從 i=0 到 i<size 遍歷並用 new_arr[i−1]+arr[i−1] 設定 new_arr[i]。
現在使用兩個 for 迴圈遍歷 new_arr[]。
現在計算 total_1 為前一個子陣列的和。以及其中的元素為 count_1。
計算 total_2 為下一個子陣列的和以及其中的元素為 count_2。
計算平均值，check_1 = total_1 / count_1; 和 check_2 = total_2 / count_2;
如果平均值 check_1 > check_2，則遞增計數。
在 for 迴圈結束時，返回計數作為結果。
示例
#include <bits/stdc++.h>
using namespace std;
int count(int arr[], int size){
int count = 0;
int new_size = size + 1;
int new_arr[new_size] = { 0 };
for (int i = 1; i < new_size; i++){
new_arr[i] = new_arr[i − 1] + arr[i − 1];
}
for (int i = 1; i < new_size; i++){
for (int j = i; j < new_size; j++){
int total_1 = new_arr[j] − new_arr[i − 1];
int count_1 = j − i + 1;
int total_2 = new_arr[size] − total_1;
int count_2 = 0;
if((size − count_1) == 0){
count_2 = 1;
} else {
count_2 = size − count_1;
}
int check_1 = total_1 / count_1;
int check_2 = total_2 / count_2;
if (check_1 > check_2){
count++;
}
}
}
return count;
}
int main(){
int arr[] = { 2, 6, 2, 4 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of number of sub−arrays such that the average of elements present in
the sub−array "<< "is greater than that not present in the sub−array are: "<<count(arr, size);
return 0;
}輸出
如果我們執行上面的程式碼，它將生成以下輸出：
Count the number of sub−arrays such that the average of elements present in the subarrayis greater than that not present in the sub-array are: 6
更新於：2021年1月5日
153 次檢視
廣告