ในบทความนี้ เราจะแก้ปัญหาในการค้นหาจำนวนอาร์เรย์ย่อยที่มีองค์ประกอบสูงสุดและต่ำสุดเหมือนกันโดยใช้ 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} and { 4,4,4 } are the subarrays which can be formed with maximum and minimum element same.
Input : array = { 3,3,1,5,1,2,2 }
Output : 9
Explanation : {3}, {3}, {1}, {5}, {1}, {2}, {2}, {3,3} and {2,2} are the subarrays which can be formed with minimum and maximum are the same. แนวทางในการหาแนวทางแก้ไข
เมื่อดูตัวอย่าง เราสามารถพูดได้ว่าจำนวนอาร์เรย์ย่อยขั้นต่ำสามารถสร้างขึ้นได้ด้วยองค์ประกอบต่ำสุดและสูงสุดที่เท่ากันกับขนาดของอาร์เรย์ จำนวนอาร์เรย์ย่อยจะเพิ่มขึ้นได้หากมีตัวเลขต่อเนื่องกัน
ดังนั้นเราจึงสามารถใช้วิธีการผ่านทุกองค์ประกอบและตรวจสอบว่าจำนวนที่ต่อเนื่องกันนั้นเหมือนกันหรือไม่และนับเพิ่มขึ้นหากหมายเลขต่อเนื่องเหมือนกันและทำลายวงในหากพบตัวเลขที่แตกต่างกัน
ตัวแปรผลลัพธ์จะเพิ่มตัวแปรผลลัพธ์ทุกครั้งที่วงในสิ้นสุดหรือแตก และสุดท้ายแสดงผลลัพธ์จากตัวแปรผลลัพธ์
ตัวอย่าง
#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(n2).
คำอธิบายของโค้ดด้านบน
ในโค้ดนี้ เราใช้ตัวแปร n เพื่อเก็บขนาดของอาร์เรย์ ผลลัพธ์ =n เนื่องจากอาร์เรย์ย่อยต่ำสุด n สามารถสร้างและนับได้เพื่อให้นับจำนวนเท่ากัน
วงนอกใช้ในการประมวลผลทุกองค์ประกอบในอาร์เรย์ วงในใช้เพื่อค้นหาจำนวนตัวเลขที่ต่อเนื่องกันหลังจากองค์ประกอบดัชนีและเพิ่มตัวแปรผลลัพธ์ด้วยตัวแปรนับทุกครั้งที่วงในสิ้นสุด ในที่สุดก็แสดงผลลัพธ์ที่เก็บไว้ในตัวแปรผลลัพธ์
แนวทางที่มีประสิทธิภาพ
ในแนวทางนี้ เราจะพิจารณาทุกองค์ประกอบ และสำหรับทุกองค์ประกอบ เรากำลังค้นหาว่ามีตัวเลขที่เหมือนกันติดต่อกันกี่จำนวน สำหรับตัวเลขที่เหมือนกันแต่ละจำนวนที่พบ เรากำลังเพิ่มตัวแปรการนับ และเมื่อพบตัวเลขที่ต่างกันโดยใช้การนับ เรากำลังค้นหาจำนวนอาร์เรย์ย่อยที่สามารถสร้างได้โดยใช้สูตร "n =n*(n+1) /2" และเพิ่มตัวแปรผลลัพธ์ด้วยคำตอบของสูตรนี้
ตัวอย่าง
#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 เท่ากับองค์ประกอบที่ดัชนีปัจจุบันหรือไม่และนับเพิ่มขึ้น 1 สำหรับจำนวนเดียวกันที่พบ หากตัวแปร temp ไม่เท่ากับองค์ประกอบดัชนี เราจะพบการรวมกันของอาร์เรย์ย่อยที่สามารถสร้างจากการนับตัวเลขเดียวกันและเก็บผลลัพธ์ไว้ในตัวแปรผลลัพธ์ เราเปลี่ยนค่า temp เป็นจำนวนการรีเซ็ตดัชนีปัจจุบันเป็น 1 ในที่สุด เรากำลังแสดงคำตอบที่เก็บไว้ในตัวแปรผลลัพธ์
บทสรุป
ในบทความนี้ เราจะแก้ปัญหาเพื่อค้นหาจำนวนอาร์เรย์ย่อยที่มีองค์ประกอบต่ำสุดและสูงสุดเท่ากัน นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ (ปกติและมีประสิทธิภาพ) โดยที่เราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ หวังว่าบทความนี้จะเป็นประโยชน์
