C++ หาจำนวน Subarray ที่ค่าต่ำสุดและสูงสุดเท่ากัน

ในบทความนี้ เราจะแก้ปัญหาการหาจำนวน Subarray ที่สมาชิกต่ำสุด (Minimum) และสูงสุด (Maximum) เหมือนกันโดยใช้ C++ นี่คือตัวอย่างสำหรับปัญหา

Input : array = { 2, 3, 6, 6, 2, 4, 4, 4 } Output : 12 Explanation : {2}, {3}, {6}, {6}, {2}, {4}, {4}, {4}, {6,6}, {4,4}, {4,4} และ { 4,4,4 } เป็น Subarray ที่ Max และ Min เหมือนกัน
Input : array = { 3,3,1,5,1,2,2 } Output : 9 Explanation : {3}, {3}, {1}, {5}, {1}, {2}, {2}, {3,3} และ {2,2} เป็น Subarray ที่ Min และ Max เหมือนกัน

วิธีการแก้ปัญหา

จากตัวอย่าง เราสามารถบอกได้ว่าจำนวน Subarray ขั้นต่ำที่สามารถสร้างได้ด้วย Min และ Max เหมือนกันเท่ากับขนาดของอาร์เรย์ จำนวน Subarray อาจมากกว่านี้ถ้ามีตัวเลขติดกันที่เหมือนกัน

ดังนั้นเราสามารถใช้วิธีการไปผ่านทุกสมาชิก และตรวจสอบว่าตัวเลขติดกันเหมือนกันหรือไม่ และเพิ่ม Count ถ้าตัวเลขติดกันเหมือนกัน และ Break ลูปในถ้าพบตัวเลขที่ต่างกัน

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

ตัวอย่าง

#include <bits/stdc++.h> 
using namespace std; 

int main(){ 
    int a[ ] = { 2, 4, 5, 3, 3, 3 }; 
    int n = sizeof(a) / sizeof(a[0]); 
    int result = n, count = 0; 
    for (int i = 0; i < n; i++) { 
        for (int j = i+1; j < n; j++) { 
            if(a[i]==a[j]) count++; 
            else break; 
        } 
        result += count; 
        count = 0; 
    } 
    cout << "Number of subarrays having minimum and maximum elements same:" << result; 
    return 0; 
}

ผลลัพธ์

Number of subarrays having minimum and maximum elements same: 9 Time complexity = O(n²).

คำอธิบายโค้ด

ในโค้ดนี้ เราใช้ตัวแปร n เก็บขนาดอาร์เรย์ result = n เพราะมี Subarray อย่างน้อย n ชุด และ count เก็บจำนวนตัวเลขที่เหมือนกัน

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

วิธีมีประสิทธิภาพ (Efficient Approach)

ในวิธีนี้ เราไปผ่านทุกสมาชิก และสำหรับแต่ละสมาชิก เราค้นหาว่ามีตัวเลขติดกันเหมือนกันกี่ตัว สำหรับแต่ละตัวที่เหมือนกัน เราเพิ่ม Count และเมื่อเจอตัวเลขที่ต่างกัน เราจะใช้ Count คำนวณจำนวน Subarray ที่สร้างได้จากสูตร "n = n*(n+1)/2" และเพิ่ม Result ด้วยคำตอบของสูตรนี้

ตัวอย่าง

#include <bits/stdc++.h> 
using namespace std; 

int main(){ 
    int a[] = { 2, 4, 5, 3, 3, 3 }; 
    int n = sizeof(a) / sizeof(a[0]); 
    int result = 0; 
    int count = 1, temp = a[0]; 
    for (int i = 1; i < n; i++) { 
        if (temp == a[i]){ 
            count++; 
        } else{ 
            temp = a[i]; 
            result = result + (count*(count+1)/2); 
            count = 1; 
        } 
    } 
    result = result + (count*(count+1)/2); 
    cout << "Number of subarrays having minimum and maximum elements same:" << result; 
    return 0; 
}

ผลลัพธ์

Number of subarrays having minimum and maximum elements same: 9 Time complexity : O(n)

คำอธิบายโค้ด

ในโค้ดนี้ เราเก็บค่าดัชนี 0 ของอาร์เรย์ไว้ในตัวแปร temp และเริ่มลูปจากดัชนี 1 เราตรวจสอบว่า temp เท่ากับสมาชิกที่ดัชนีปัจจุบันหรือไม่ และเพิ่ม Count 1 สำหรับตัวเลขที่เหมือนกัน ถ้า temp ไม่เท่ากับสมาชิกดัชนีปัจจุบัน เราหาการจัดหมู่ของ Subarray ที่สร้างได้จาก Count ของตัวเลขที่เหมือนกัน และเก็บผลลัพธ์ใน Result เปลี่ยนค่า Temp เป็นดัชนีปัจจุบัน รีเซ็ต Count เป็น 1 สุดท้าย เราแสดงคำตอบที่เก็บในตัวแปร Result

สรุป

ในบทความนี้ เราแก้ปัญหาการหา Number of subarrays whose minimum and maximum elements are the same เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้ และวิธีแก้ปัญหา (ทั่วไปและมีประสิทธิภาพ) ซึ่งเราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่น เช่น C, Java, Python ได้ หวังว่าจะเป็นประโยชน์