ค้นหาจำนวนอาร์เรย์ย่อยที่มี m เลขคี่โดยใช้ C++

หากคุณเคยใช้ C ++ คุณต้องรู้ว่าอาร์เรย์ย่อยคืออะไรและมีประโยชน์อย่างไร อย่างที่เราทราบดีว่าในภาษา C++ เราสามารถแก้ปัญหาทางคณิตศาสตร์หลาย ๆ อย่างได้อย่างง่ายดาย ดังนั้นในบทความนี้ เราจะอธิบายข้อมูลทั้งหมดเกี่ยวกับวิธีที่เราสามารถค้นหาเลขคี่ M โดยใช้อาร์เรย์ย่อยเหล่านี้ใน C++

ในปัญหานี้ เราจำเป็นต้องค้นหาอาร์เรย์ย่อยจำนวนมากที่สร้างด้วยอาร์เรย์และจำนวนเต็มที่กำหนด โดยที่แต่ละอาร์เรย์ย่อยประกอบด้วย m เลขคี่พอดี นี่คือตัวอย่างง่ายๆ ของแนวทางนี้ −

Input : array = { 6,3,5,8,9 }, m = 2
Output : 5
Explanation : Subarrays with exactly 2 odd numbers are
{ 3,5 }, { 6,3,5 }, { 3,5,8 }, { 5,8,9 }, { 6,3,5,8 }, { 3,5,8,9 }

Input : array = { 1,6,3,2,5,4 }, m = 2
Output : 6
Explanation : Subarrays with exactly 2 odd numbers are
{ 1,6,3 }, { 3,2,5 }, { 1,6,3,2 }, { 6,3,2,5 }, { 3,2,5,4 }, { 6,3,2,5,4 }

แนวทางแรก

ในแนวทางนี้ อาร์เรย์ย่อยที่เป็นไปได้ทั้งหมดจะถูกสร้างขึ้นจากอาร์เรย์ที่กำหนด และแต่ละอาร์เรย์ย่อยจะถูกตรวจสอบหาค่า m เลขคี่พอดี เป็นวิธีการสร้างและค้นหาที่ง่าย และความซับซ้อนของเวลาของแนวทางนี้คือ O(n ² )

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int main (){
    int a[] = { 1, 6, 3, 2, 5, 4 };
    int n = 6, m = 2, count = 0; // n is size of array, m numbers to be find in subarrays,
                              // count is number of subarray with m odd numbers
    for (int i = 0; i < n; i++){ // outer loop to process each element.
        int odd = 0;
        for (int j = i; j < n; j++) {// inner loop to find subarray with m number
            if (a[j] % 2)
                odd++;
            if (odd == m) // if odd numbers become equals to m.
                count++;
        }
    }
    cout << "Number of subarrays with n numbers are: " << count;
    return 0;
}

ผลลัพธ์

Number of subarrays with n numbers are: 6

คำอธิบายของโค้ดด้านบน

ในโค้ดนี้ เราใช้การวนซ้ำแบบซ้อนเพื่อค้นหาอาร์เรย์ย่อยที่มี m เลขคี่ และวงรอบนอกจะใช้เพื่อเพิ่ม "i" ซึ่งจะใช้ในการประมวลผลแต่ละองค์ประกอบในอาร์เรย์

วงในถูกใช้เพื่อค้นหาอาร์เรย์ย่อยและประมวลผลองค์ประกอบจนกระทั่งตัวนับคี่ถึง m เพิ่มจำนวนตัวนับผลลัพธ์สำหรับแต่ละอาร์เรย์ย่อยที่พบ และสุดท้ายพิมพ์ผลลัพธ์ที่เก็บไว้ในตัวแปรการนับ

แนวทางที่สอง

อีกวิธีหนึ่งคือการสร้างอาร์เรย์สำหรับเก็บจำนวนนำหน้าด้วย "i" ตัวเลขคี่ ประมวลผลทุกองค์ประกอบ และเพิ่มจำนวนเลขคี่สำหรับทุกๆ จำนวนคี่ที่พบ

เมื่อจำนวนเลขคี่เกินหรือเท่ากับ m ให้เพิ่มตัวเลขที่ตำแหน่ง (odd - m ) ในอาร์เรย์นำหน้า

เมื่อคี่มีค่ามากกว่าหรือเท่ากับ m เราจะคำนวณจำนวนอาร์เรย์ย่อยที่เกิดขึ้นจนกว่าดัชนีและตัวเลข "odd - m" จะถูกเพิ่มลงในตัวแปรการนับ ผลลัพธ์จะถูกเก็บไว้ในตัวแปรการนับหลังจากประมวลผลทุกองค์ประกอบแล้ว

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int main (){
    int array[ ] = { 1, 6, 3, 2, 5, 4 };
    int n = 6, m = 2, count = 0, odd = 0, i;
    int prefix_array[n + 1] = { 0 };
    // outer loop to process every element of array
    for (i = 0; i < n; i++){
        prefix_array[odd] = prefix_array[odd] + 1;    // implementing value at odd index in prefix_array[ ]
        // if array element is odd then increment odd variable
        if (array[i] % 2 == 0)
            odd++;
        // if Number of odd element becomes equal or greater than m
        //  then find the number of possible subarrays that can be formed till the index.
        if (odd >= m)
            count += prefix_array[odd - m];
    }
    cout << "Number of subarrays with n numbers are: " << count;
    return 0;
}

ผลลัพธ์

Number of subarrays with n numbers are: 6

คำอธิบายของโค้ดด้านบน

การเริ่มต้นอาร์เรย์และตัวแปรด้วยค่าเริ่มต้น -

int array[ 6 ] = { 1, 6, 3, 2, 5, 4 };
int n = 6, m = 2, count = 0, odd = 0, i;
int prefix_array[n + 1] = { 0 };

ในที่นี้ เรากำลังเริ่มต้นตัวแปร n ด้วยขนาดของอาร์เรย์ m ด้วยจำนวนเลขคี่เพื่อค้นหา นับด้วย 0 เพื่อนับจำนวนอาร์เรย์ย่อยที่เป็นไปได้ คี่ด้วย 0 และ prefix_array ขนาด n + 1 ด้วย 0

ทำความเข้าใจวงจร

for (i = 0; i < n; i++){
   prefix_array[odd] = prefix_array[odd] + 1;
   if (array[i] % 2 == 0)
      odd++;
      if (odd >= m)
         count += prefix_array[odd - m];
}

ในลูปนี้ เรากำลังใช้ค่าที่ดัชนีคี่ใน prefix_array[ ] จากนั้นจึงเพิ่มตัวแปรคี่หากพบตัวเลขคี่ เราพบว่าจำนวนอาร์เรย์ย่อยสามารถเกิดขึ้นได้จนถึงดัชนีเมื่อตัวแปรคี่มีค่าเท่ากับหรือมากกว่า m

สุดท้าย เราพิมพ์อาร์เรย์ย่อยจำนวนหนึ่งด้วย m ตัวเลขคี่ที่เก็บไว้ในตัวแปรนับและรับผลลัพธ์

บทสรุป

ในบทความนี้ เราเข้าใจวิธีการหาจำนวนอาร์เรย์ย่อยที่มี m เลขคี่จากสองวิธี -

• สร้างทุก subarray และตรวจสอบหา m เลขคี่ในนั้น และเพิ่มจำนวนสำหรับ subarray แต่ละตัวที่พบ ความซับซ้อนของเวลาของรหัสนี้คือ O(n2)

• วิธีที่มีประสิทธิภาพ ซึ่งจะผ่านแต่ละองค์ประกอบของอาร์เรย์และสร้างอาร์เรย์ส่วนนำหน้า และค้นหาผลลัพธ์โดยใช้อาร์เรย์ส่วนนำหน้า ความซับซ้อนของเวลาของรหัสนี้คือ O(n)

หวังว่าบทความนี้จะเป็นประโยชน์ในการทำความเข้าใจปัญหาและแนวทางแก้ไข