สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มที่ไม่ได้เรียงลำดับขนาด N งานคือหาองค์ประกอบ max และ second max ที่แตกต่างกันซึ่งมีอยู่ในอาร์เรย์ อาร์เรย์อาจมีองค์ประกอบซ้ำกันด้วย ดังนั้นเราต้องหาเฉพาะองค์ประกอบที่แตกต่างกัน ตัวอย่างเช่น
ตัวอย่างอินพุต 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 และ second 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 เป็นองค์ประกอบที่แตกต่างกันในอาร์เรย์ซึ่งเป็นค่าสูงสุดและค่าสูงสุดอันดับสอง
