資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中非遞增子陣列的計數
給定一個包含正整數的陣列arr[]。目標是找到長度至少為1且非遞增的子陣列的數量。如果arr[]= {1,3,2}，則子陣列將是{1}，{2}，{3}，{3,2}。計數為4。
例如
輸入
arr[] = {5,4,5}輸出
Count of number of non-increasing subarrays are: 7
解釋
The subarrays will be −
{5}, {4}, {5}, {5,4}輸入
arr[] = {10,9,8,7}輸出
Count of number of non−increasing subarrays are − 10
解釋
The subarrays will be −
{10}, {9}, {8}, {7}, {10,9}, {9,8}, {8,7}, {10,9,8}, {9,8,7}, {10,9,8,7}以下程式中使用的演算法如下：
在此方法中，我們將利用這樣一個事實：如果arr[]中索引i和j之間的元素不是非遞增的，則索引i到j+1、i到j+2……i到j+n-1之間的元素永遠不可能是非遞增的，因此只要元素是非遞增的，就繼續增加這個子陣列的長度。如果找到任何較小的元素arr[j]<arr[j-1]，則將len*(len+1)/2（包含len個元素的當前非遞增子陣列的子陣列數量）新增到計數這些子陣列中，並將子陣列的長度重置為1。
取一個整數陣列arr[]。
函式subarrays(int arr[], int size)接收陣列及其大小，並返回非遞增子陣列的數量。
將初始計數設為0，並將最小子陣列的長度設為temp=1。
使用for迴圈遍歷arr[]，如果arr[i + 1] <= arr[i]，則遞增temp，因為子陣列是非遞增的。
否則，將(temp + 1) * temp) / 2新增到計數中，表示長度為temp的非遞增子陣列的子陣列數量。
為新的子陣列設定temp=1。
在所有迴圈結束時，如果長度temp>1，則再次將(temp + 1) * temp) / 2新增到計數中，表示最後一個子陣列。
返回計數作為結果。
示例
#include <bits/stdc++.h>
using namespace std;
int subarrays(int arr[], int size){
int count = 0;
int temp = 1;
for(int i = 0; i < size − 1; ++i){
if (arr[i + 1] <= arr[i]){
temp++;
} else {
count += (((temp + 1) * temp) / 2);
temp = 1;
}
}
if(temp > 1){
count += (((temp + 1) * temp) / 2);
}
return count;
}
int main(){
int arr[] = {2, 6, 1, 8, 3};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of number of non−increasing subarrays are: "<<subarrays(arr, size);
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出：
Count the number of non-increasing subarrays are: 7
更新於：2021年1月5日
286 次瀏覽
廣告