นับอาร์เรย์ย่อยที่มีองค์ประกอบทั้งหมดมากกว่า K ใน C++

เราได้รับอาร์เรย์ arr[] ของจำนวนเต็ม ยังเป็นตัวเลข K เป้าหมายคือการนับอาร์เรย์ย่อยทั้งหมดของ arr[] เพื่อให้องค์ประกอบทั้งหมดของอาร์เรย์ย่อยมีค่ามากกว่า K หรือ K น้อยกว่าองค์ประกอบทั้งหมดของอาร์เรย์ย่อย หากอาร์เรย์คือ [1,2,3] และ K คือ 1 อาร์เรย์ย่อยจะเป็น [2], [3], [2,3]

ให้เราเข้าใจด้วยตัวอย่าง

ป้อนข้อมูล − arr[] ={ 2, 2, 1, 1, 1, 5 }; K=1

ผลผลิต − จำนวนอาร์เรย์ย่อยที่มีองค์ประกอบทั้งหมดมากกว่า K คือ − 4

คำอธิบาย − Subaarays จะเป็น:[2], [2], [5], [2,2] องค์ประกอบทั้งหมดในอาร์เรย์ย่อยแต่ละรายการมีค่ามากกว่า 1

ป้อนข้อมูล − arr[] ={ 3,4,5,6 }; K=2

ผลผลิต − จำนวนอาร์เรย์ย่อยที่มีองค์ประกอบทั้งหมดมากกว่า K คือ − 10

คำอธิบาย − Subaaray จะเป็น − [3], [4], [5], [6], [3,4], [4,5], [5,6], [3,4,5], [4, 5,6], [3,4,5,6]. นับรวม=10.

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

เราจะสำรวจอาร์เรย์โดยใช้ a for a loop หากองค์ประกอบปัจจุบันมีค่ามากกว่า K ให้นับเพิ่ม มิฉะนั้นจะตั้งค่า count=0 และ total=count*(count+1)/2 (สำหรับอาร์เรย์ย่อย) ถ้าตอนท้ายนับไม่เป็นศูนย์ เพิ่ม count*(count+1)/2 สำหรับการนับอาร์เรย์ย่อยที่เหลืออยู่

• นำอาร์เรย์ arr[] ของตัวเลข

• ฟังก์ชัน sub_greater_k(int arr[], int size, int k) รับอาร์เรย์และส่งกลับจำนวนอาร์เรย์ย่อยที่มีองค์ประกอบทั้งหมดมากกว่า k

• นับเริ่มต้นเป็น 0

• เราจะสำรวจอาร์เรย์โดยใช้ for loops จาก i=0 ถึง i

• ถ้า arr[i]>k ก็นับการเพิ่มขึ้น

• อาร์เรย์ย่อยที่มีการนับ (องค์ประกอบ> k ) จะถูกนับ*(count+1)/2 บวกกับผลรวมของอาร์เรย์ย่อยดังกล่าวทั้งหมด

• ต่อท้ายอีก ให้บวก count*(count+)/2 กับยอดรวม ถ้าการนับไม่ใช่ศูนย์

• คืนยอดรวมตามผลลัพธ์

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int sub_greater_k(int arr[], int size, int k){
   int count = 0;
   int total = 0;
   for (int i = 0; i < size; i++){
      if (arr[i] > k){
         count++;
      }
      else{
         total += (count) * (count + 1) / 2;
         count = 0;
      }
   }
   if(count){
      total += (count) * (count + 1) / 2;
   }
   return total;
}
int main(){
   int arr[] = {2, 4, 6, 1, 3, 7, 9 };
   int size = sizeof(arr) / sizeof(arr[0]);
   int k = 7;
   cout<<"Count of subarrays with all elements greater than K are: "<<sub_greater_k(arr, size, k);
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count of subarrays with all elements greater than K are: 1