เรียงอาร์เรย์ที่แปลงแล้วใน C++

สมมติว่ามีอาร์เรย์จำนวนเต็มที่เรียงแล้ว nums และค่าจำนวนเต็ม a, b และ c เราต้องนำฟังก์ชันควอдраติก f(x) = ax^2 + bx + c ไปใช้กับแต่ละสมาชิก x ในอาร์เรย์ และอาร์เรย์สุดท้ายต้องเรียงลำดับแล้ว

เช่น ถ้าอินพุทเป็น nums = [-4,-2,2,4], a = 1, b = 3, c = 5 ผลลัพธ์จะเป็น [3,9,15,33]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −

• กำหนดฟังก์ชัน f() รับ x, a, b, c −

• คืนค่า ax^2 + bx + c

• จากเมธอดหลักทำดังนี้ −

• n := ขนาดของ nums

• start := 0, end := n - 1

• กำหนดอาร์เรย์ ret ขนาด n

• ถ้า a >= 0 แล้ว −

  • ลูป i := n - 1 ถึง 0 ลดลงทีละ 1 ทำ −

    • x := f(nums[start], a, b, c)

    • y := f(nums[end], a, b, c)

    • ถ้า x > y แล้ว −

      • เพิ่ม start ขึ้น 1

      • ret[i] := x

    • มิฉะนั้น

      • ret[i] := y

      • ลด end ลง 1

• มิฉะนั้น

  • ลูป i := 0 ถึง n-1 ทำ −

    • x := f(nums[start], a, b, c)

    • y := f(nums[end], a, b, c)

    • ถ้า x < y แล้ว −

      • เพิ่ม start ขึ้น 1

      • ret[i] := x

    • มิฉะนั้น

      • ret[i] := y

      • ลด end ลง 1

• คืนค่า ret

ตัวอย่าง

ลองดูการติดตั้งต่อไปนี้เพื่อให้เข้าใจได้ดีขึ้น −

#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;    } }; main(){    Solution ob;    vector<int> v = {-4,-2,2,4};    print_vector(ob.sortTransformedArray(v, 1, 3, 5)); }

อินพุท

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

เอาต์พุท

[3, 9, 15, 33, ]