จำนวนอาร์เรย์ย่อยของขนาด K และค่าเฉลี่ยมากกว่าหรือเท่ากับเกณฑ์ใน C++

สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม arr และจำนวนเต็มสองจำนวน k และขีดจำกัด เราต้องหาจำนวนอาร์เรย์ย่อยของขนาด k และค่าเฉลี่ยที่มากกว่าหรือเท่ากับเกณฑ์ ดังนั้นหากอินพุตมีลักษณะดังนี้:[2,2,2,2,5,5,5,8] และ k =3 และขีดจำกัด =4 ผลลัพธ์จะเป็น 3 เนื่องจากอาร์เรย์ย่อย [2,5,5] , [5,5,5] และ [5,5,8] มีค่าเฉลี่ย 4, 5 และ 6 ตามลำดับ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• sum :=0, div :=k และ n :=จำนวนองค์ประกอบในอาร์เรย์

• set sum :=ผลรวมขององค์ประกอบทั้งหมดของ arr

• ยกเลิก :=0

• สำหรับ i :=0 และ j ในช่วง k ถึง n – 1 ให้เพิ่มทั้ง i และ j ขึ้น 1

  • ถ้า sum / div>=threshold ให้เพิ่มความละเอียดขึ้น 1

  • ลดผลรวมโดย arr[i]

  • เพิ่มผลรวมโดย arr[j]

• ถ้า sum / div>=threshold ให้เพิ่ม ret ขึ้น 1

• รีเทิร์น.

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int numOfSubarrays(vector<int>& arr, int k, int threshold) {
      double sum = 0;
      double div = k;
      int n = arr.size();
      for(int i = 0; i < k; i++){
         sum += arr[i];
      }
      int ret = 0;
      for(int i = 0, j = k; j < n; i ++, j++){
         if(sum / div >= threshold ){
            ret++;
         }
         sum -= arr[i];
         sum += arr[j];
      }
      if(sum / div >= threshold ){
         ret++;
      }
      return ret;
   }
};
main(){
   vector<int> v = {2,2,2,2,5,5,5,8};
   Solution ob;
   cout << (ob.numOfSubarrays(v, 3, 4));
}

อินพุต

[2,2,2,2,5,5,5,8]
3
4

ผลลัพธ์

3