Hitung subarray panjang K yang min melebihi median tatasusunan yang diberikan

Ungkapan "subarray panjang K" terpakai kepada subarray bersebelahan dengan unsur K tepat. Menguasai dan menggunakan subarray adalah penting untuk menyelesaikan pelbagai masalah dalam bidang seperti pengaturcaraan dinamik, geometri pengiraan dan analisis data.

Satu lagi konsep penting dalam operasi tatasusunan dan statistik ialah median. Median tatasusunan mewakili nilai di tengah apabila elemen diisih dalam tertib menaik. Apabila terdapat bilangan elemen genap, median ialah purata dua nilai pusat. Median membentuk ukuran kecenderungan memusat yang berterusan kerana ia kurang terdedah kepada nilai ekstrem atau outlier daripada min.

Kertas kerja ini cuba mengkaji cabaran menentukan bilangan subarray panjang K dalam tatasusunan tertentu yang min melebihi median. Dengan memahami hubungan antara min dan median set data, kita boleh menyelidiki cabaran ini dan membangunkan teknik yang cekap untuk menyelesaikannya. Sertai kami semasa kami membedah penyataan masalah, memeriksa konsep utama dan secara efisien mengira bilangan subarray panjang K yang diperlukan dalam tatasusunan.

Tatabahasa

Isih elemen dalam tatasusunan dalam tertib menaik.

sort(begin(array), end(array))

Isytiharkan vektor integer.

vector<int> vec
</int>

Isytihar tatasusunan integer

int arr[]

Asas untuk sintaks gelung dalam C++.

for(int i=0; i<size; ++i)

Algoritma kod sumber

• Baca tatasusunan input dan saiznya.

• Kira median tatasusunan yang diberi.

• Untuk setiap subarray panjang K, kira purata.

• Bandingkan min dengan median.

• Subarray statistik yang min melebihi median.

Kaedah 1: Brute force cracking

Kaedah 1 membentuk penyelesaian mudah kepada cabaran menentukan bilangan subarray panjang K yang min melebihi median tatasusunan yang ditentukan. Pada mulanya, tatasusunan input diisih dan median dikira. Selepas itu, atur cara melelar melalui semua subarray K-panjang yang boleh dilaksanakan dan mengira puratanya dengan mengagregatkan komponennya. Jika min subarray melebihi median, kiraan akan ditambah. Akhirnya, kod tersebut mengembalikan bilangan subarray tersebut.

Algoritma

• Kira median tatasusunan yang diberi.

• Lelaran ke atas semua subarray panjang K yang mungkin.

• Kira purata setiap sub-tatasusunan.

• Jika min subarray lebih besar daripada median, tambahkan kiraan.

Contoh 1

Kod di bawah mengikut pendekatan brute force yang dinyatakan sebelum ini dalam artikel ini. Ia mula-mula menyusun tatasusunan input dan mengira median. Ia kemudian melelang ke atas semua subarray panjang K yang mungkin dan mengira puratanya dengan menjumlahkan elemennya. Jika min subarray lebih besar daripada median, kiraan akan ditambah. Akhirnya, kod tersebut mengembalikan kiraan subarray tersebut.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int countSubarrays(vector<int> &arr, int n, int k) {
   int count = 0;
   double median;
   sort(arr.begin(), arr.end());
   median = (n % 2 == 0) ? (arr[n/2 - 1] + arr[n/2]) / 2.0 : arr[n/2];

   for (int i = 0; i <= n - k; i++) {
      double sum = 0;
      for (int j = i; j < i + k; j++) {
         sum += arr[j];
      }
      if (sum / k > median) {
         count++;
      }
   }
   return count;
}

int main() {
   vector<int> arr = {1, 5, 6, 7, 9};
   int n = arr.size();
   int k = 3;
   int result = countSubarrays(arr, n, k);
   cout << "Number of K-length subarrays with average exceeding median: " << result << endl;
   return 0;
}

Output

Number of K-length subarrays with average exceeding median: 1

Kaedah 2: Kaedah pengoptimuman

Kaedah 2 ialah penyelesaian yang elegan untuk masalah menentukan bilangan subarray panjang K dengan min melebihi median tatasusunan yang ditentukan. Ia mula-mula menyusun tatasusunan input dan mengira median. Ia kemudiannya mengira tatasusunan jumlah awalan, yang digunakan untuk menentukan jumlah setiap subray panjang K. Algoritma melelaran ke atas semua subarray K-panjang yang mungkin, mengira puratanya menggunakan tatasusunan jumlah awalan dan membandingkan dengan median.

Jika min subarray melebihi median, kiraan akan dinaikkan. Akhirnya, program ini mengembalikan bilangan subarray tersebut. Pendekatan ini lebih cekap daripada pendekatan pertama kerana ia menggunakan tatasusunan jumlah awalan untuk mengira jumlah setiap subarray panjang K, sekali gus mengurangkan kerumitan masa jalan.

Algoritma

• Kira median tatasusunan yang diberi.

• Kira awalan dan tatasusunan.

• Lelaran ke atas semua subarray panjang K yang mungkin.

• Kira purata menggunakan awalan dan tatasusunan.

• Jika min subarray lebih besar daripada median, tambahkan kiraan.

Contoh 2

Algoritma ini mengikut pendekatan terbaik yang diterangkan sebelum ini. Ia memanfaatkan tatasusunan jumlah awalan untuk mengira agregat dengan cepat untuk setiap subset panjang K. Selepas urutan input diisih dan nilai median ditentukan, jumlah awalan dikira. Atur cara kemudian menggelungkan semua subset panjang K, mengira puratanya menggunakan tatasusunan jumlah awalan dan membandingkannya dengan median. Jika min melebihi median, kiraan akan ditambah. Secara ringkasnya, kod tersebut mengembalikan bilangan subset tersebut.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int countSubarrays(vector<int> &arr, int n, int k) {
   int count = 0;
   double median;
   sort(arr.begin(), arr.end());
   median = (n % 2 == 0) ? (arr[n/2 - 1] + arr[n/2]) / 2.0 : arr[n/2];

   vector<int> prefix_sum(n);
   prefix_sum[0] = arr[0];
   for (int i = 1; i < n; i++) {
      prefix_sum[i] = prefix_sum[i - 1] + arr[i];
   }

   for (int i = 0; i <= n - k; i++) {
      double sum = (i == 0) ? prefix_sum[i + k - 1] : prefix_sum[i + k - 1] - prefix_sum[i - 1];
      if (sum / k > median) {
         count++;
      }
   }
   return count;
}

int main() {
   vector<int> arr = {1, 5, 6, 7, 9};
   int n = arr.size();
   int k = 3;
   int result = countSubarrays(arr, n, k);
   cout << "Number of K-length subarrays with average exceeding median: " << result << endl;
   return 0;
}

Output

Number of K-length subarrays with average exceeding median: 1

Kesimpulan

Dalam artikel ini, kami membincangkan dua cara untuk mengira subarray K-panjang yang min melebihi median tatasusunan yang diberikan menggunakan C++. Kaedah pertama ialah kaedah brute force, yang berulang ke atas semua subarray panjang K yang mungkin dan mengira puratanya. Kaedah kedua ialah pengoptimuman yang menggunakan awalan dan tatasusunan untuk mengira purata dengan lebih cekap. Kedua-dua kod disediakan dan boleh dilaksanakan untuk mencari bilangan subarray yang diperlukan.

Atas ialah kandungan terperinci Hitung subarray panjang K yang min melebihi median tatasusunan yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!