C++-এ অ্যারেতে K স্ট্রongesতম মান বের করা

একটি অ্যারে arr এবং ইন্টিজার k দেওয়া আছে। একটি মান arr[i] অন্য মান arr[j] চেয়ে স্ট্রংগার যদি |arr[i] - m| > |arr[j] - m|, এখানে m হলো অ্যারের মেডিয়ান। যদি দুটির পার্থক্য সমান হয়, তবে বড় মানটিই স্ট্রংগার। আমাদের টপ k স্ট্রংগার মান বের করতে হবে।

ইনপুট: arr = [1,2,3,4,5], k = 2 → আউটপুট: [5,1] (মেডিয়ান ৩, স্ট্রেংথ অনুযায়ী সর্টেড: [5,1,4,2,3])

সমাধানের ধাপগুলো:

• অ্যারে সর্ট করব

• m := arr[(n-1)/2] (মেডিয়ান)

• দুটি পয়েন্টার i=0, j=n-1 দিয়ে দুই কোণ থেকে তুলনা করব

• k বার লুপ চালাব:

  • x1 = |arr[j]-m|, x2 = |arr[i]-m|

  • যদি x1 >= x2 হয়, তবে arr[j] নিব এবং j--

  • অন্যথায় arr[i] নিব এবং i++

উদাহরণ

নিচের কোডটি দেখুন −

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

void print_vector(vector<int> v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) {
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    int calc(int x, int m) {
        return abs(x - m);
    }
    vector<int> getStrongest(vector<int>& arr, int k) {
        sort(arr.begin(), arr.end());
        int n = arr.size();
        int m = arr[(n - 1) / 2];
        int i = 0, j = n - 1;
        vector<int> ret;
        while (k--) {
            int x1 = calc(arr[j], m);
            int x2 = calc(arr[i], m);
            if (x1 >= x2) {
                ret.push_back(arr[j]);
                j--;
            } else {
                ret.push_back(arr[i]);
                i++;
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,3,4,5};
    print_vector(ob.getStrongest(v, 2));
}

ইনপুট

{1,2,3,4,5},2

আউটপুট

[5, 1, ]