Tulis kod menggunakan C++ untuk mencari bilangan subarray dengan nilai minimum dan maksimum yang sama

Dalam artikel ini, kami akan menggunakan C++ untuk menyelesaikan masalah mencari bilangan sub-array yang nilai maksimum dan minimumnya adalah sama. Berikut adalah contoh masalah ini −

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.

Cara menyelesaikannya

Dengan contoh, kita boleh katakan bahawa bilangan minimum sub-tatasusunan boleh dibentuk menggunakan elemen minimum dan maksimum yang sama bersamaan dengan saiz tatasusunan. Bilangan subarray boleh menjadi lebih besar jika nombor berturut-turut adalah sama.

Jadi, kita boleh menggunakan kaedah melintasi setiap elemen dan menyemak sama ada nombor berturut-turut adalah sama, jika nombor berturut-turut adalah sama, jika nombor yang berbeza ditemui, ganggu gelung dalam.

Setiap kali gelung dalam tamat atau terganggu, pembolehubah hasil dinaikkan dan akhirnya pembolehubah hasil dipaparkan.

p>

Contoh

#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;
}

Output

Number of subarrays having minimum and maximum elements same: 9
Time complexity = O(n<sup>2</sup>).

Penjelasan kod di atas

Dalam kod ini, kami menggunakan pembolehubah n untuk menyimpan saiz tatasusunan, hasil = n, kerana sekurang-kurangnya n sub-tatasusunan boleh dibentuk dan bilangan yang dikira sama.

Gelung luar digunakan untuk memproses setiap elemen dalam tatasusunan. Gelung dalam digunakan untuk mencari bilangan nombor yang sama berturut-turut selepas elemen indeks dan pada penghujung gelung dalam ia menambah pembolehubah kiraan bersama-sama dengan pembolehubah hasil. Akhirnya output yang disimpan dalam pembolehubah hasil dipaparkan.

Kaedah yang cekap

Dalam kaedah ini kita mengulangi setiap elemen dan untuk setiap elemen kita mencari bilangan nombor yang sama berturut-turut. Bagi setiap nombor yang sama ditemui, kami menambah pembolehubah kiraan dan apabila nombor yang berbeza ditemui, ketahui berapa banyak subarray boleh dibentuk menggunakan formula "n = n*(n+1)/2" Tambah pembolehubah hasil.

Contoh

#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;
}

Output

Number of subarrays having minimum and maximum elements same: 9
Time complexity : O(n)

Penerangan kod di atas

Dalam kod ini, kami menyimpan indeks ke-0 tatasusunan dalam pembolehubah temp dan memulakan gelung dari indeks 1. Kami menyemak sama ada pembolehubah temp adalah sama dengan elemen pada indeks semasa dan menambah kiraan sebanyak 1 untuk nombor yang sama ditemui. Jika pembolehubah temp tidak sama dengan elemen indeks, kita dapati gabungan subarray yang boleh diperoleh dengan mengira nombor yang sama dan menyimpan hasilnya dalam pembolehubah hasil. Kami menukar nilai sementara kepada indeks semasa, menetapkan semula kiraan kepada 1. Akhir sekali, kami memaparkan jawapan yang disimpan dalam pembolehubah hasil.

Kesimpulan

Dalam artikel ini, kami menyelesaikan masalah untuk mencari bilangan subarray yang elemen minimum dan maksimumnya adalah sama. Kami juga mempelajari program C++ untuk menyelesaikan masalah ini dan cara lengkap untuk menyelesaikan masalah ini (biasa dan cekap). Kita boleh menulis program yang sama dalam bahasa lain seperti C, java, python dan bahasa lain. Semoga artikel ini bermanfaat kepada anda.

Atas ialah kandungan terperinci Tulis kod menggunakan C++ untuk mencari bilangan subarray dengan nilai minimum dan maksimum yang sama. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!