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

สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มและค่าจำนวนเต็ม 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 −

• ขวานกลับ^2 + bx + c

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

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

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

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

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

  • สำหรับการเริ่มต้น i :=n - 1 เมื่อ i>=0, อัปเดต (ลด i โดย 1) ให้ทำ -

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

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

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

      • (เพิ่มขึ้นเริ่มต้น 1)

      • ret[i] :=x

    • มิฉะนั้น

      • ret[i] :=y

      • (ลดทีละ 1)

• มิฉะนั้น

  • สำหรับการเริ่มต้น i :=0 เมื่อ i

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

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

    • ถ้า x

      • (เพิ่มขึ้นเริ่มโดย 1)

      • ret[i] :=x

    • มิฉะนั้น

      • ret[i] :=y

      • (ลดทีละ 1)

• รีเทิร์น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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, ]