資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學使用 C++ 查詢最小值和最大值相同的子陣列個數
在本文中，我們將解決使用 C++ 查詢最大和最小元素相同的子陣列個數的問題。以下是這個問題的示例：
Input : array = { 2, 3, 6, 6, 2, 4, 4, 4 }
Output : 12
Explanation : {2}, {3}, {6}, {6}, {2}, {4}, {4}, {4}, {6,6}, {4,4}, {4,4} and { 4,4,4 } are the subarrays which can be formed with maximum and minimum element same.
Input : array = { 3,3,1,5,1,2,2 }
Output : 9
Explanation : {3}, {3}, {1}, {5}, {1}, {2}, {2}, {3,3} and {2,2} are the subarrays which can be formed with minimum and maximum are the same.解決方案方法
觀察示例，我們可以說，可以形成的最小子陣列個數等於陣列的大小，其最小和最大元素相同。如果存在連續相同的數字，則子陣列個數可能會更多。
因此，我們可以採用一種方法，遍歷每個元素，並檢查其連續數字是否相同，如果連續數字相同則遞增計數器，如果找到不同的數字則中斷內迴圈。
每次內迴圈結束或中斷時，結果變數都會遞增，最後顯示結果變數中的結果。
示例
#include <bits/stdc++.h>
using namespace std;
int main(){
int a[ ] = { 2, 4, 5, 3, 3, 3 };
int n = sizeof(a) / sizeof(a[0]);
int result = n, count =0;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if(a[i]==a[j])
count++;
else
break;
}
result+=count;
count =0;
}
cout << "Number of subarrays having minimum and maximum elements same:" << result;
return 0;
}輸出
Number of subarrays having minimum and maximum elements same: 9 Time complexity = O(n2).
上述程式碼的解釋
在此程式碼中，我們使用變數 n 來儲存陣列的大小，result = n，因為至少可以形成 n 個子陣列，並使用計數器來計數相同的數字。
外迴圈用於處理陣列中的每個元素。內迴圈用於查詢索引元素之後有多少個連續的數字相同，並在每次內迴圈結束時使用計數變數遞增結果變數。最後顯示儲存在結果變數中的輸出。
高效方法
在這種方法中，我們遍歷每個元素，併為每個元素搜尋有多少個連續的相同數字。對於每個找到的相同數字，我們遞增計數變數，當找到不同的數字時，我們使用公式 **“n = n*(n+1)/2”** 來計算可以使用相同數字形成的子陣列組合數，並將結果變數遞增該公式的結果。
示例
#include <bits/stdc++.h>
using namespace std;
int main(){
int a[] = { 2, 4, 5, 3, 3, 3 };
int n = sizeof(a) / sizeof(a[0]);
int result = 0;
int count =1,temp=a[0];
for (int i = 1; i < n; i++) {
if (temp==a[i]){
count++;
}
else{
temp=a[i];
result = result + (count*(count+1)/2);
count=1;
}
}
result = result + (count*(count+1)/2);
cout << "Number of subarrays having minimum and maximum elements same:" << result;
return 0;
}輸出
Number of subarrays having minimum and maximum elements same: 9 Time complexity : O(n)
上述程式碼的解釋
在此程式碼中，我們將陣列的第 0 個索引儲存在 temp 變數中，並從索引 1 開始迴圈。我們檢查 temp 變數是否等於當前索引處的元素，併為找到的相同數字遞增計數器。如果 temp 變數不等於索引元素，那麼我們找到可以從相同數字的計數中生成的子陣列組合，並將結果儲存在結果變數中。我們將 temp 值更改為當前索引，並將計數器重置為 1。最後，我們顯示儲存在結果變數中的答案。
結論
在本文中，我們解決了一個問題，即查詢最小和最大元素相同的子陣列個數。我們還學習了針對此問題的 C++ 程式以及我們解決此問題的完整方法（普通方法和高效方法）。我們可以使用 C、Java、Python 和其他語言編寫相同的程式。希望本文對您有所幫助。
437 次瀏覽
