Phần tử lớn thứ K trong mảng (Kth Largest Element)

Giới thiệu

Từ một tập dữ liệu, thuật toán này sẽ tìm phần tử lớn nhất đến phần tử lớn thứ k của mảng.

Bài toán này có thể giải quyết dễ dàng bằng cách sắp xếp mảng. Ta có thể sắp xếp theo thứ tự tăng dần hoặc giảm dần. Giải theo thứ tự giảm dần, ta có thể lấy k phần tử đầu tiên để tìm kết quả.

Đầu vào và Đầu ra

Đầu vào: Các phần tử mảng: {1, 23, 12, 9, 30, 2, 50, 63, 87, 12, 45, 21}, K = 4
Đầu ra: 4 phần tử lớn nhất là 87 63 50 45

Thuật toán

kthLargestElement(array, n, k)
Đầu vào: Mảng, số phần tử trong mảng, vị trí k.
Đầu ra: Hiển thị phần tử lớn nhất đến phần tử lớn thứ k của mảng.

Begin
    sắp xếp mảng theo thứ tự giảm dần
    for i := 0 to k-1, do
        hiển thị array[i]
    done
End

Ví dụ (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++)  // lớn nhất đến lớn thứ k
        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);
}

Kết quả

87 63 50 45