ในปัญหานี้ เราได้รับ unsorted array งานคือหา 3 ตัวเลขมากที่สุด
ตัวอย่าง
Input: arr[] = {7, 3, 9, 12, 1} Output: 12, 9, 7
วิธีที่ 1: Single Pass O(N) - เก็บ max, max2, max3
void findThreeLargest(int arr[], int n) {
int max = arr[0], max2 = arr[0], max3 = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) { max3 = max2; max2 = max; max = arr[i]; }
else if (arr[i] > max2) { max3 = max2; max2 = arr[i]; }
else if (arr[i] > max3) max3 = arr[i];
}
cout << max << ", " << max2 << ", " << max3;
}
วิธีที่ 2: เรียงลำดับ O(N log N)
#include <bits/stdc++.h>
using namespace std;
void findThreeLargest(int arr[], int n) {
sort(arr, arr + n, greater());
int count = 0;
for (int i = 0; i < n && count < 3; i++) {
if (i == 0 || arr[i] != arr[i-1]) {
cout << arr[i] << " ";
count++;
}
}
}
ผลลัพธ์
Three largest elements are 86 53 50
(จาก array: 15, 2, 7, 86, 0, 21, 50, 53, 50)
