อาร์เรย์ย่อยเป็นส่วนที่อยู่ติดกันของอาร์เรย์ ตัวอย่างเช่น เราพิจารณาอาร์เรย์ [5, 6, 7, 8] จากนั้นจะมีอาร์เรย์ย่อยที่ไม่ว่างเปล่าสิบรายการ เช่น (5), (6), (7), (8), (5, 6), (6 ,7), (7,8), (5,6,7), (6,7,8) และ (5,6,7,8)
ในคู่มือนี้ เราจะอธิบายทุกข้อมูลที่เป็นไปได้เพื่อค้นหาจำนวนอาร์เรย์ย่อยที่มีผลรวมคี่ใน C++ ในการค้นหาจำนวนอาร์เรย์ย่อยด้วยผลรวมคี่ เราสามารถใช้วิธีการต่างๆ ได้ ดังนั้นนี่คือตัวอย่างง่ายๆ −
Input : array = {9,8,7,6,5}
Output : 9
Explanation :
Sum of subarray -
{9} = 9
{7} = 7
{5} = 5
{9,8} = 17
{8,7} = 15
{7,6} = 13
{6,5} = 11
{8,7,6} = 21
{9,8,7,6,5} = 35 แนวทางกำลังเดรัจฉาน
ด้วยวิธีการนี้ เราสามารถตรวจสอบได้ว่าผลรวมขององค์ประกอบในอาร์เรย์ย่อยทั้งหมดเป็นคู่หรือคี่ หากเป็นจำนวนคู่ เราจะปฏิเสธอาร์เรย์ย่อยนั้นและจะนับอาร์เรย์ย่อยด้วยผลรวมคี่ วิธีนี้ไม่ใช่วิธีที่มีประสิทธิภาพเนื่องจากความซับซ้อนของโค้ดนี้คือ O (n 2 )
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int main(){
int n=5, temp = 0;
int a[n-1] = { 9,8,7,6,5 } ; // declaring our array.
int cnt = 0; // counter variable.
for(int i = 0; i < n; i++){
temp = 0; // refreshing our temp sum.
for(int j = i; j < n; j++){ // this loop will make our subarrays starting from i till n-1.
temp = temp + a[j];
if( temp % 2 == 1 )
cnt++;
}
}
cout << "Number of subarrays with odd sum : " << cnt << "\n";
return 0;
} ผลลัพธ์
Number of subarrays with odd sum : 9
คำอธิบายของโค้ดด้านบน
ลูปที่ซ้อนกันถูกใช้ในโค้ดนี้โดยที่วงรอบนอกถูกใช้เพื่อเพิ่มค่าของ I ซึ่งชี้ไปที่แต่ละค่าของอาร์เรย์ตั้งแต่เริ่มต้น วงในจะใช้เพื่อค้นหาอาร์เรย์ย่อยที่เริ่มต้นจากตำแหน่ง " i " มีผลรวมคี่
แนวทางที่มีประสิทธิภาพ
ในแนวทางนี้ เรากำลังประมวลผลทุกองค์ประกอบจากตำแหน่งที่ 0 ในอาร์เรย์ หากองค์ประกอบปัจจุบันเป็นเลขคี่ ให้เพิ่มตัวนับคี่และเพิ่มตัวนับคู่สำหรับทุกเลขคู่ หากเราพบเลขคี่ ให้สลับค่าของคู่และคี่เพราะการเพิ่มตัวเลขคี่ในอาร์เรย์ย่อยจะเปลี่ยนพาริตีและสุดท้ายจะเพิ่มจำนวนให้กับผลลัพธ์ ความซับซ้อนของรหัสนี้คือ O(n) เนื่องจากเรากำลังประมวลผลทุกองค์ประกอบ
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int main(){
int odd = 0, even = 0, result = 0,n=5,i,temp;
int arr[ n-1 ] = { 9,8,7,6,5}; // initialising the array
// for loop for processing every element of array
for ( i = 0 ; i < n ; i ++ ) {
if ( arr[ i ] % 2 == 0 ) {
even++;
} else {
// swapping even odd values
temp = even;
even = odd;
odd = temp + 1;
}
result += odd;
}
cout << "Number of subarrays with odd sum : " << result;
} ผลลัพธ์
Number of subarrays with odd sum : 9
คำอธิบายของโค้ดด้านบน
ในรหัสนี้ เราตรวจสอบทุกองค์ประกอบเพื่อหาคู่/คี่และเพิ่มตัวนับสำหรับจำนวนคู่และตัวนับคี่สำหรับจำนวนคี่ นอกจากนี้ เรากำลังสลับค่าตัวนับเลขคู่คี่ หากพบเลขคี่ มิฉะนั้น มันจะเปลี่ยนพาริตีของ subarray จากนั้นจึงเพิ่มค่าของตัวนับคี่ให้กับตัวแปรผลลัพธ์หลังจากการวนซ้ำทุกครั้ง
บทสรุป
ในบทความนี้ เราได้อธิบายวิธีหาจำนวนอาร์เรย์ย่อยที่มีค่ารวมคี่จากวิธี Brute force ซึ่งจะสร้างอาร์เรย์ย่อยทุกรายการด้วยผลรวมคี่และเพิ่มจำนวนขึ้น ความซับซ้อนของเวลาของรหัสนี้คือ O(n2) วิธีที่มีประสิทธิภาพคือผ่านแต่ละองค์ประกอบของอาร์เรย์และเพิ่มตัวแปรตัวนับคี่/คู่ด้วยทุก ๆ จำนวนคี่/คู่ที่พบและสลับตัวนับหากพบจำนวนคี่ ความซับซ้อนของเวลาของรหัสนี้คือ O(n) หวังว่าบทความนี้จะเป็นประโยชน์ในการทำความเข้าใจปัญหาและแนวทางแก้ไข
