บทนำ
จากชุดข้อมูล อัลกอริทึมนี้จะหาองค์ประกอบที่ใหญ่ที่สุดถึงอันดับ k ของอาเรย์
ปัญหานี้แก้ได้ง่ายโดยการเรียงลำดับอาเรย์ สามารถเรียงได้ทั้ง ascending หรือ descending หากเรียง descending เราจะได้ k อิลิเมนต์แรกเป็นผลลัพธ์
อินพุตและเอาต์พุต
Input: องค์ประกอบของอาเรย์: {1, 23, 12, 9, 30, 2, 50, 63, 87, 12, 45, 21}, K = 4
Output: องค์ประกอบ 4 อันดับแรกคือ 87 63 50 45
อัลกอริทึม
kthLargestElement(array, n, k)
Input: อาเรย์, จำนวนองค์ประกอบในอาเรย์, ตำแหน่ง k
Output: แสดงองค์ประกอบที่ใหญ่ที่สุดถึงอันดับ k ของอาเรย์
Begin
เรียงอาเรย์ใน descending order
for i := 0 to k-1, do
display array[i]
done
End
ตัวอย่างโค้ด (C++)
#include <iostream>
#include <algorithm>
using namespace std;
bool compare(int a, int b) {
return a > b;
}
void kthLargestElement(int array[], int n, int k) {
sort(array, array+n, compare);
for (int i = 0; i < k; i++) // ใหญ่ที่สุดถึง k-th largest
cout << array[i] << " ";
}
int main() {
int array[] = {1, 23, 12, 9, 30, 2, 50, 63, 87, 12, 45, 21};
int n = 12;
int k = 4;
kthLargestElement(array, n, k);
}
ผลลัพธ์
87 63 50 45
