Question

360. Sort Transformed Array

中文文档

Description

Given a sorted integer array nums and three integers a, b and c, apply a quadratic function of the form f(x) = ax2 + bx + c to each element nums[i] in the array, and return _the array in a sorted order_.

 

Example 1:

Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]

Example 2:

Input: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
Output: [-23,-5,1,7]

 

Constraints:

• 1 <= nums.length <= 200
• -100 <= nums[i], a, b, c <= 100
• nums is sorted in ascending order.

 

Follow up: Could you solve it in O(n) time?

Solutions

Solution 1

class Solution:
  def sortTransformedArray(
    self, nums: List[int], a: int, b: int, c: int
  ) -> List[int]:
    def f(x):
      return a * x * x + b * x + c

    n = len(nums)
    i, j, k = 0, n - 1, 0 if a < 0 else n - 1
    res = [0] * n
    while i <= j:
      v1, v2 = f(nums[i]), f(nums[j])
      if a < 0:
        if v1 <= v2:
          res[k] = v1
          i += 1
        else:
          res[k] = v2
          j -= 1
        k += 1
      else:
        if v1 >= v2:
          res[k] = v1
          i += 1
        else:
          res[k] = v2
          j -= 1
        k -= 1
    return res

class Solution {
  public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
    int n = nums.length;
    int i = 0, j = n - 1, k = a < 0 ? 0 : n - 1;
    int[] res = new int[n];
    while (i <= j) {
      int v1 = f(a, b, c, nums[i]), v2 = f(a, b, c, nums[j]);
      if (a < 0) {
        if (v1 <= v2) {
          res[k] = v1;
          ++i;
        } else {
          res[k] = v2;
          --j;
        }
        ++k;
      } else {
        if (v1 >= v2) {
          res[k] = v1;
          ++i;
        } else {
          res[k] = v2;
          --j;
        }
        --k;
      }
    }
    return res;
  }

  private int f(int a, int b, int c, int x) {
    return a * x * x + b * x + c;
  }
}

class Solution {
public:
  vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
    int n = nums.size();
    int i = 0, j = n - 1, k = a < 0 ? 0 : n - 1;
    vector<int> res(n);
    while (i <= j) {
      int v1 = f(a, b, c, nums[i]), v2 = f(a, b, c, nums[j]);
      if (a < 0) {
        if (v1 <= v2) {
          res[k] = v1;
          ++i;
        } else {
          res[k] = v2;
          --j;
        }
        ++k;
      } else {
        if (v1 >= v2) {
          res[k] = v1;
          ++i;
        } else {
          res[k] = v2;
          --j;
        }
        --k;
      }
    }
    return res;
  }

  int f(int a, int b, int c, int x) {
    return a * x * x + b * x + c;
  }
};

func sortTransformedArray(nums []int, a int, b int, c int) []int {
  n := len(nums)
  i, j, k := 0, n-1, 0
  if a >= 0 {
    k = n - 1
  }
  res := make([]int, n)
  for i <= j {
    v1, v2 := f(a, b, c, nums[i]), f(a, b, c, nums[j])
    if a < 0 {
      if v1 <= v2 {
        res[k] = v1
        i++
      } else {
        res[k] = v2
        j--
      }
      k++
    } else {
      if v1 >= v2 {
        res[k] = v1
        i++
      } else {
        res[k] = v2
        j--
      }
      k--
    }
  }
  return res
}

func f(a, b, c, x int) int {
  return a*x*x + b*x + c
}