เราได้รับอาร์เรย์ arr[] ที่มีจำนวนเต็มและตัวแปร X เป้าหมายคือการนับอาร์เรย์ย่อยทั้งหมดของ arr[] เพื่อให้แต่ละอาร์เรย์ย่อยประกอบด้วยองค์ประกอบที่น้อยกว่าหรือเท่ากับ X เท่านั้น ตัวอย่างเช่น หากอาร์เรย์คือ [1 2,3] และ X=2 จากนั้นอาร์เรย์ย่อยจะเป็น [1], [2] และ [1,2]
ให้เราเข้าใจด้วยตัวอย่าง
ป้อนข้อมูล − arr[] ={ 4,3,2,1,6 }; X=3
ผลผลิต − จำนวนอาร์เรย์ย่อยที่มีองค์ประกอบน้อยกว่าหรือเท่ากับ X คือ − 6
คำอธิบาย − Subaarays จะเป็น -
[3], [2], [1], [3,2], [2,1], [3,2,1]
ป้อนข้อมูล − arr[] ={ 3,6,2,7,1,8,5 }; X=5
ผลผลิต − จำนวนอาร์เรย์ย่อยที่มีองค์ประกอบน้อยกว่าหรือเท่ากับ X คือ − 4
คำอธิบาย − Subaarays จะเป็น -
[3], [2], [1], [5]
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
เรากำลังสร้างอาร์เรย์ไบนารี temp_arr[] ที่มีขนาดเท่ากับอาร์เรย์ arr[] ดั้งเดิม อาร์เรย์ไบนารีนี้จะมี 1 หาก arr[i] ที่สัมพันธ์กันมีค่าน้อยกว่าหรือเท่ากับ X มิฉะนั้น 0 ตอนนี้ให้สำรวจ temp_arr[] และตรวจสอบความต่อเนื่องของ 1 ( องค์ประกอบที่น้อยกว่า X ใน arr[] ) เก็บความยาวของแต่ละ subarray ดังกล่าวในอุณหภูมิ สำหรับอาร์เรย์ของอุณหภูมิความยาว อาร์เรย์ย่อยทั้งหมดจะเป็น temp*(temp+1)/2 เพิ่มสิ่งนี้ในการนับรวมและดำเนินการต่อจนจบ temp_arr[].
-
ใช้อาร์เรย์ arr[] และตัวแปร X
-
ฟังก์ชัน sub_X(int arr[], int size, int x) รับอาร์เรย์และ x และคืนค่าจำนวนอาร์เรย์ย่อยที่มีเฉพาะองค์ประกอบที่น้อยกว่าหรือเท่ากับ x
-
ใช้อุณหภูมิตัวแปรชั่วคราวและผลรวมสุดท้ายของอาร์เรย์ย่อยดังกล่าวเป็นการนับ
-
ใช้อาร์เรย์ไบนารี temp_arr[] ที่มีความยาวเท่ากับ arr[]
-
เราจะสำรวจอาร์เรย์ arr[] โดยใช้ for loop จาก i=0 ถึง i
-
สำหรับแต่ละองค์ประกอบ arr[i]<=x ให้ตั้งค่า temp_arr[i]=1 อื่น 0
-
สำรวจ temp_arr[] โดยใช้ for loop.
-
หากองค์ประกอบใด ๆ temp_arr[i] ==1 จากนั้นสำรวจโดยใช้ลูปย่อยจากดัชนีปัจจุบัน i จนถึง temp_arr[temp_2] ( temp_2=i+1; temp_2
-
การนับอาร์เรย์ย่อยที่มี 1 ทั้งหมดจะเป็น temp=temp_2-i
-
อาร์เรย์ย่อยนี้มี 1 ทั้งหมดซึ่งหมายความว่าองค์ประกอบทั้งหมดใน arr[i] คือ <=x อาร์เรย์ย่อยทั้งหมดจะเป็น temp_3=temp*(temp+1)/2.
-
ในตอนท้ายของการสำรวจทั้งสอง การนับจะมีจำนวนการนับรวมของอาร์เรย์ย่อยทั้งหมดภายใน arr ที่มีตัวเลขน้อยกว่าหรือเท่ากับ x
ตัวอย่าง
#include <iostream>
using namespace std;
int sub_X(int arr[], int size, int x){
int count = 0, temp = 0;
int temp_arr[size];
for (int i = 0; i < size; i++){
if (arr[i] <= x){
temp_arr[i] = 1;
}
else{
temp_arr[i] = 0;
}
}
for (int i = 0; i < size; i++){
if (temp_arr[i] == 1){
int temp_2;
for(temp_2 = i + 1; temp_2 < size; temp_2++){
if(temp_arr[temp_2] != 1){
break;
}
}
temp = temp_2 - i;
int temp_3 = (temp) * (temp + 1)/2;
count = count + temp_3;
i = temp_2;
}
}
return count;
}
int main(){
int arr[] = { 2, 6, 1, 10, 5, 3 };
int x = 4;
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of sub-arrays which have elements less than or equal to X are: "<<sub_X(arr, size, x);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count of sub-arrays which have elements less than or equal to X are: 3
