C++ में सॉर्ट ट्रांसफॉर्म्ड एरे - द्विघात फलन लागू करें

समस्या विवरण

मान लीजिए हमारे पास पूर्णांकों की एक सॉर्ट की गई सरणी nums और पूर्णांक मान a, b और c हैं। हमें सरणी में प्रत्येक तत्व x पर f(x) = ax^2 + bx + c रूप का एक द्विघात फलन लागू करना है। और अंतिम सरणी सॉर्ट क्रम में होनी चाहिए।

उदाहरण के लिए, यदि इनपुट nums = [-4,-2,2,4], a = 1, b = 3, c = 5 है, तो आउटपुट [3,9,15,33] होगा।

समाधान दृष्टिकोण

द्विघात फलन के गुणों का उपयोग करके दो-पॉइंटर दृष्टिकोण:

1. फ़ंक्शन f(x, a, b, c) परिभाषित करें जो ax^2 + bx + c लौटाता है
2. n := nums का आकार, start := 0, end := n - 1
3. आकार n की सरणी ret परिभाषित करें
4. यदि a >= 0 (ऊपर की ओर खुलता है):
   • i को n-1 से 0 तक घटाते हुए:
     • x := f(nums[start]), y := f(nums[end])
     • यदि x > y, तो start++, ret[i] := x
     • अन्यथा ret[i] := y, end--
5. अन्यथा (नीचे की ओर खुलता है):
   • i को 0 से n-1 तक बढ़ाते हुए:
     • x := f(nums[start]), y := f(nums[end])
     • यदि x < y, तो start++, ret[i] := x
     • अन्यथा ret[i] := y, end--
6. ret लौटाएं

C++ कार्यान्वयन

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

void print_vector(vector<auto> 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; 
        int 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, ]