使用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.

求解的方法

透過範例，我們可以說，使用等於陣列大小的相同最小和最大元素可以形成最小數量的子數組。如果連續的數字相同，子數組的數量可以更多。

所以我們可以採用遍歷每個元素，檢查其連續的數字是否相同的方法，如果連續的數字則增加計數相同，如果發現不同的數字則中斷內循環。

每次內循環結束或中斷時，結果變數都會增加結果變量，最後顯示結果變數的結果。

p>

範例

#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(n<sup>2</sup>).

以上程式碼的解釋

#在這段程式碼中，我們使用變數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 變數是否等於該元素在目前索引處，對於找到的相同數字將計數加 1。如果 temp 變數不等於索引元素，則我們找到可以透過相同數字的計數得出的子數組的組合，並將結果儲存在 result 變數中。我們將臨時值變更為目前索引，將計數重設為 1。最後，我們顯示儲存在結果變數中的答案。

結論

在本文中，我們解決了一個問題尋找最小和最大元素相同的子數組的數量。我們也學習了解決這個問題的C 程序以及解決這個問題的完整方法（正常且有效率）。我們可以用其他語言像是C、java、python等語言來寫同樣的程式。希望這篇文章對您有幫助。

以上是使用C++編寫程式碼，找到具有相同最小值和最大值的子數組的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！