একটি সোর্টেড ইন্টিজার অ্যারে nums এবং তিনটি ইন্টিজার a, b, c দেওয়া আছে। প্রতিটি এলিমেন্ট x এর জন্য কোড্রেটিক ফাংশন f(x) = ax² + bx + c প্রয়োগ করতে হবে এবং ফলাফল অ্যারেটিও সোর্টেড ক्रमে রিটার্ন করতে হবে।
উদাহরণ
ইনপুট: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
আউটপুট: [3, 9, 15, 33]
সমাধানের পদ্ধতি (Two Pointers + Parabola Property)
কোড্রেটিক ফাংশন একটি পারাবোলা। a > 0 হলে এটি উপরে খোলা (minimum ở মাঝপথে, maximum দুটি кінারায়)। a < 0 হলে নিচে খোলা (maximum মাঝপথে, minimum দুটি кінারায়)। এই প্রোপার্টি ব্যবহার করে টু পয়েন্টার দিয়ে O(n) তে সমাধান করা যায়।
f(x) = ax² + bx + cফাংশন ডিফাইন করুন।start = 0, end = n-1এবং রেজাল্ট অ্যারেret[n]।- যদি
a >= 0(উপরে খোলা):i = n-1থেকে0পর্যন্ত পিছিয়ে যান।x = f(nums[start]), y = f(nums[end])বের করুন।- বড় মানটি
ret[i]-এ রাখুন এবং সংশ্লিষ্ট পয়েন্টার মুভ করুন।
- যদি
a < 0(নিচে খোলা):i = 0থেকেn-1পর্যন্ত এগিয়ে যান।- ছোট মানটি
ret[i]-এ রাখুন এবং সংশ্লিষ্ট পয়েন্টার মুভ করুন।
retরিটার্ন করুন।
C++ কোড উদাহরণ
#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 f(int x, int a, int b, int c) {
return a * x * x + b * x + c;
}
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
int n = nums.size();
int start = 0, end = n - 1;
vector<int> ret(n);
if (a >= 0) {
for (int i = n - 1; i >= 0; i--) {
int x = f(nums[start], a, b, c);
int y = f(nums[end], a, b, c);
if (x > y) {
start++;
ret[i] = x;
} else {
ret[i] = y;
end--;
}
}
} else {
for (int i = 0; i < n; i++) {
int x = f(nums[start], a, b, c);
int y = f(nums[end], a, b, c);
if (x < y) {
start++;
ret[i] = x;
} else {
ret[i] = y;
end--;
}
}
}
return ret;
}
};
int main() {
Solution ob;
vector<int> v = {-4,-2,2,4};
print_vector(ob.sortTransformedArray(v, 1, 3, 5));
return 0;
}
ইনপুট
{-4,-2,2,4}, 1, 3, 5
আউটপুট
[3, 9, 15, 33, ]
