Trung vị sau khi thêm K số nguyên trong C++

Trong bài toán này, chúng ta được cho một mảng n số nguyên và thêm K phần tử vào mảng, sau đó tìm trung vị của mảng kết quả. Cho điều kiện N + K là số lẻ.

Hãy xem một ví dụ để hiểu bài toán:

Đầu vào –

mảng = {23, 65, 76, 67} ; k = 1

Đầu ra –

67

Để giải quyết bài toán này, chúng ta sẽ sắp xếp các phần tử cho trước theo thứ tự tăng dần và sau đó thêm K phần tử vào cuối mảng, tức là lấy K phần tử lớn hơn.

Điều kiện cho là N + K là lẻ. Vì vậy, trung vị có thể tính bằng công thức: (N + K) / 2.

Ví dụ

Chương trình tìm trung vị:

#include <bits/stdc++.h>
using namespace std;
int findMedianAfterK(int arr[], int n, int K) {
    sort(arr, arr + n);
    return arr[((n + K)/2)];
}
int main() {
    int array[] = {3, 56, 8, 12, 67, 10 };
    int k = 3;
    int n = sizeof(array) / sizeof(array[0]);
    cout<<"Trung vị sau khi thêm "<<k<<" phần tử là "<<findMedianAfterK(array, n, k);
    return 0;
}

Kết quả

Trung vị sau khi thêm 3 phần tử là 56