Kth องค์ประกอบที่ใหญ่ที่สุดในอาร์เรย์

จากชุดข้อมูล อัลกอริธึมนี้จะค้นหาองค์ประกอบที่ใหญ่ที่สุดไปจนถึงองค์ประกอบที่ใหญ่ที่สุดอันดับที่ k ของอาร์เรย์

ปัญหานี้สามารถแก้ไขได้ง่าย ๆ โดยการเรียงลำดับอาร์เรย์ เราสามารถเรียงลำดับได้ทั้งจากน้อยไปมากหรือจากมากไปหาน้อย การแก้ปัญหาโดยเรียงลำดับจากมากไปน้อย เราจะได้ k องค์ประกอบแรกเพื่อค้นหาผลลัพธ์

อินพุตและเอาต์พุต

Input:
The elements of an array: {1, 23, 12, 9, 30, 2, 50, 63, 87, 12, 45, 21}, K = 4
Output:
4 largest elements are 87 63 50 45

อัลกอริทึม

kthLargestElement(array, n, k)

ป้อนข้อมูล: อาร์เรย์ จำนวนองค์ประกอบในอาร์เรย์ ให้วาง k

ผลลัพธ์: แสดงองค์ประกอบที่ใหญ่ที่สุดถึงองค์ประกอบที่ใหญ่ที่สุดที่ k ของอาร์เรย์

Begin
   sort the array in descending order
   for i := 0 to k-1, do
      display array[i]
   done
End

ตัวอย่าง

#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++)    //largest to kth largest element
      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