資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中計算元素差值為1的連續子陣列個數
給定一個包含整數的陣列arr[]。目標是計算arr[]的所有子陣列的個數，使得每個子陣列中連續元素之間的差值僅為1。如果陣列是[1,2,3]，子陣列將只有[1,2]，[2,3]，[1,2,3]。
讓我們透過例子來理解。
輸入 − arr[] = { 4,3,2,1 };
輸出 − 元素差值為1的連續子陣列個數為 − 6
解釋 − 子陣列將為 −
[4,3], [3,2], [2,1], [4,3,2], [3,2,1], [4,3,2,1]. Total 6.
輸入 − arr[] = { 1,5,6,7,9,11 };
輸出 − 元素差值為1的連續子陣列個數為 − 3
解釋 − 子陣列將為 −
[5,6], [6,7], [5,6,7]. Total 3
下面程式中使用的方法如下
我們將使用for迴圈遍歷陣列。從i=0到i<size。然後檢查是否有任何元素與其相鄰元素的差值為1。如果是，則將索引儲存為first。如果不是，則將子陣列中的元素個數作為temp (first-last +1)。索引first和last之間的陣列都具有差值為1的連續元素。因此，子陣列總數將為temp*(temp-1)/2。將其新增到count中。為下一個所有連續元素的陣列更新索引first=last=i。
取一個數字陣列arr[]。
函式sub_ele_diff_one(int arr[], int size)接受陣列並返回差值為1的連續子陣列的個數。
將初始計數設定為0。
我們將使用for迴圈遍歷陣列，從i=0到I <size。
取兩個變數first、last為0，表示所有元素連續且差值為1的索引。
檢查arr[i-1]-arr[i] ==1 OR arr[i]-arr[i-1]==1。（元素差值為1）。如果為真，則遞增first。
如果之前的條件為假，則滿足此條件的陣列中的元素總數為temp=first-last+1。可能的子陣列總數為total=temp*(temp-1)/2。
現在將此子陣列計數total新增到count中。
使用當前I（連續元素條件失敗的索引）更新索引first和last。
在for迴圈結束時，如果first!=last。這意味著剩餘的陣列滿足條件。應用相同的步驟並將total新增到count中。
在兩個迴圈結束時，返回count作為結果。
示例
#include <iostream>
using namespace std;
int sub_ele_diff_one(int arr[], int size){
int count = 0, first = 0, last = 0;
for (int i = 1; i < size; i++){
if (arr[i] - arr[i - 1] == 1 || arr[i-1] - arr[i] == 1){
first++;
}
else{
int temp = first - last + 1;
int total = temp * (temp - 1) / 2;
count = count + total;
first = i;
last = i;
}
}
if (first != last){
int temp = first - last + 1;
int total = temp * (temp - 1) / 2;
count = count + total;
}
return count;
}
int main(){
int arr[] = { 1, 2, 4, 3 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of Subarrays with Consecutive elements differing by 1 are: "<<sub_ele_diff_one(arr, size);
return 0;
}輸出
如果我們執行上面的程式碼，它將生成以下輸出：
Count of Subarrays with Consecutive elements differing by 1 are: 2
232 次瀏覽
