Sắp xếp mảng đã biến đổi trong C ++

Giả sử chúng ta có một mảng được sắp xếp gồm các số nguyên và các giá trị nguyên a, b và c. Ta phải áp dụng một hàm bậc hai có dạng f (x) =ax ^ 2 + bx + c cho mỗi phần tử x trong mảng. Và mảng cuối cùng phải được sắp xếp theo thứ tự.

Vì vậy, nếu đầu vào giống như nums =[-4, -2,2,4], a =1, b =3, c =5, thì đầu ra sẽ là [3,9,15,33]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định hàm f (), nhận x, a, b, c -

• trả về ax ^ 2 + bx + c

• Từ phương thức chính, hãy làm như sau -

• n:=kích thước của nums

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

• Xác định ret mảng có kích thước n

• nếu a> =0, thì -

  • để khởi tạo i:=n - 1, khi i> =0, cập nhật (giảm i đi 1), thực hiện -

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

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

    • nếu x> y, thì -

      • (tăng bắt đầu lên 1)

      • ret [i]:=x

    • Nếu không

      • ret [i]:=y

      • (giảm cuối xuống 1)

• Nếu không

  • để khởi tạo i:=0, khi i

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

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

    • nếu x

      • (tăng bắt đầu lên 1)

      • ret [i]:=x

    • Nếu không

      • ret [i]:=y

      • (giảm cuối xuống 1)

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Đầu ra

[3, 9, 15, 33, ]