Tìm k phần tử lớn nhất của mảng giữ nguyên thứ tự ban đầu trong C++

Cho mảng arr[] n phần tử. Nhiệm vụ: tìm k phần tử lớn nhất giữ nguyên thứ tự xuất hiện.

Ví dụ:

Đầu vào: arr[] = {5, 1, 3, 6, 2}, k = 2

Đầu ra: 5, 6

Giải thích:

Hai phần tử lớn nhất là 6 và 5. 5 xuất hiện trước 6 nên in 5 trước.

Phương pháp giải

Tạo bản sao mảng, sắp xếp giảm dần. Duyệt mảng gốc, nếu phần tử có trong k phần tử lớn nhất của bản sao thì in ra.

Chương trình minh họa

Ví dụ

#include <bits/stdc++.h>
using namespace std;

bool seachVal(int decArr[], int k, int ele) {
    for (int i = 0; i < k; i++) {
        if (decArr[i] == ele)
            return true;
    }
    return false;
}

void printKMaxEle(int arr[], int k, int n) {
    int decArr[n];
    for (int i = 0; i < n; i++) {
        decArr[i] = arr[i];
    }
    sort(decArr, decArr + n, greater<int>());
    for (int i = 0; i < n; ++i)
        if (seachVal(decArr, k, arr[i]))
            cout << arr[i] << " ";
}

int main() {
    int arr[] = { 15, 1, 3, 6, 2, 34, 8, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << k << " maximum elements of the array in their original order are \n";
    printKMaxEle(arr, k, n);
    return 0;
}

Kết quả

3 maximum elements of the array in their original order are 15 34 9