สมมติว่าเราได้ให้อาร์เรย์ของจำนวนเต็มขนาด N ที่ไม่ได้จัดเรียง ภารกิจคือการค้นหาองค์ประกอบสูงสุดและค่าสูงสุดที่สองที่แตกต่างกันซึ่งมีอยู่ในอาร์เรย์ อาร์เรย์อาจมีองค์ประกอบที่ซ้ำกันด้วย ดังนั้นเราจึงต้องหาองค์ประกอบที่แตกต่างกันเท่านั้น ตัวอย่างเช่น
อินพุต-1 −
N = 5
A[ ] = { 2, 2, 1, 3, 4 } ผลผลิต −
4 3
คำอธิบาย − จากอาร์เรย์ที่กำหนด เราจะเห็นว่า '4' คือค่าสูงสุด และ '3' คือค่าสูงสุดอันดับสอง
อินพุต-2 −
N = 4
A[ ] = { 1,3,3,2 } ผลผลิต −
3 2
คำอธิบาย จากอาร์เรย์ขนาด 4 ที่กำหนด เราจะเห็นว่า '3' ใหญ่ที่สุดและ '2' มีขนาดใหญ่เป็นอันดับสอง ดังนั้นเราจะคืนค่า 3 2 เป็นเอาต์พุต
แนวทางการแก้ปัญหานี้
ในอาร์เรย์ขนาด N ที่กำหนด อาจมีองค์ประกอบที่ซ้ำกันบางส่วนด้วย ในการค้นหาองค์ประกอบสูงสุดและอันดับสองจากอาร์เรย์ เราสามารถเริ่มต้นตัวแปรสองตัวที่เก็บค่าสูงสุดและค่าสูงสุดที่สองได้
ในขั้นต้น หากองค์ประกอบปัจจุบันมากกว่าค่าสูงสุด เราจะเก็บค่าของมันไว้ที่ค่าสูงสุด และค่าของค่าสูงสุด (ก่อนหน้า) เป็นค่าสูงสุดอันดับสอง
เพื่อค้นหาองค์ประกอบที่แตกต่าง เราจะตรวจสอบว่าองค์ประกอบปัจจุบันมีค่าเท่ากับสูงสุดหรือไม่ หากค่าปัจจุบันไม่เท่ากับค่าสูงสุดและมากกว่าค่าสูงสุดที่สองด้วย เราจะแทนที่ค่าก่อนหน้าของค่าสูงสุดที่สองด้วยค่าปัจจุบัน
-
เริ่มต้นและรับอินพุตขนาด N ของอาร์เรย์
-
ฟังก์ชัน maxAndSecondMax(int arr[], int size) รับอาร์เรย์เป็นอินพุตและขนาดของอาร์เรย์ ซึ่งส่งคืนองค์ประกอบสูงสุดและสูงสุดที่สองของอาร์เรย์ที่กำหนด
-
วนซ้ำองค์ประกอบอาร์เรย์และค้นหาว่าองค์ประกอบปัจจุบันมากกว่าค่าสูงสุด จากนั้นเก็บค่าปัจจุบันไว้ที่ค่าสูงสุดและค่าก่อนหน้าของค่าสูงสุดด้วยค่าสูงสุดที่สอง
-
มิฉะนั้น หากค่าปัจจุบันมากกว่าค่าสูงสุดที่สอง ให้แทนที่ค่าก่อนหน้าด้วยค่าปัจจุบัน นอกจากนี้ มูลค่าปัจจุบันไม่ควรเท่ากับสูงสุด
-
ตรวจสอบว่าค่าสูงสุดที่สองไม่มีค่าใดๆ หรือไม่
-
คืนค่า max และ max ที่สองเป็นผลลัพธ์สุดท้าย
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
void maxAndSecondMax(int *arr, int size){
int max= INT_MIN;
int s_max= INT_MIN;
for(int i=0;i<size; ++i){
if(arr[i] >max){
s_max= max;
max= arr[i];
}
else if(arr[i]> s_max && arr[i]!= max){
s_max= arr[i];
}
}
if(s_max==INT_MIN){
s_max= -1;
}
cout<<max<<" "<<s_max;
}
int main(){
int N= 6;
int A[N]= {1,3,2,5,6,3};
maxAndSecondMax(A,N);
return 0;
} ผลลัพธ์
หากเราจะเรียกใช้โค้ดข้างต้น ก็จะพิมพ์ผลลัพธ์เป็น
6 5
6 และ 5 เป็นองค์ประกอบที่แตกต่างกันในอาร์เรย์ซึ่งเป็นค่าสูงสุดและค่าสูงสุดอันดับสอง
