Question

360. 有序转化数组

English Version

题目描述

给你一个已经 排好序 的整数数组 nums 和整数 a 、 b 、 c 。对于数组中的每一个元素 nums[i] ，计算函数值 f(_x_) = _ax_2 + _bx_ + c ，请 _按升序返回数组_ 。

 

示例 1：

输入: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
输出: [3,9,15,33]

示例 2：

输入: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
输出: [-23,-5,1,7]

 

提示：

• 1 <= nums.length <= 200
• -100 <= nums[i], a, b, c <= 100
• nums 按照 升序排列

 

进阶：你可以在时间复杂度为 O(n) 的情况下解决这个问题吗？

解法

方法一

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
}