LeetCode [360] Sort Transformed Array

 360. Sort Transformed Array

Medium

Given a sorted array of integers nums and integer values a, b and c. Apply a quadratic function of the form f(x) = ax2 + bx + c to each element x in the array.

The returned array must be in sorted order.

Expected time complexity: O(n)

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]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

public class Solution { public int[] sortTransformedArray(int[] nums, int a, int b, int c) { int n = nums.length; int[] sorted = new int[n]; int i = 0, j = n - 1; int index = a >= 0 ? n - 1 : 0; while (i <= j) { if (a >= 0) { sorted[index--] = quad(nums[i], a, b, c) >= quad(nums[j], a, b, c) ? quad(nums[i++], a, b, c) : quad(nums[j--], a, b, c); } else { sorted[index++] = quad(nums[i], a, b, c) >= quad(nums[j], a, b, c) ? quad(nums[j--], a, b, c) : quad(nums[i++], a, b, c); } } return sorted; } private int quad(int x, int a, int b, int c) { return a * x * x + b * x + c; } }

YMSF

2. given a sorted list x, a function f(x) = a*x^2+b*x+c, return a list of y = f(x) in sorted order.

要求 O(N) complexity

是有点，需要考虑下 a，b大于，小于和等于0的情况。然后用two pointer找下一个更大的数就好了

//   蠡口安全商

public int[] sortTransformedArray(int[] nums, int a, int b, int c) {

    int n = nums.length, d = a >= 0 ? 1 : -1, start = (n - 1) / 2 * (d + 1);

    int[] ans = new int[n];

    for (int i = 0, j = n - 1; i <= j; start -= d) {

      ans[start] = f(nums, a, b) * d >= f(nums[j], a, b) * d ? f(nums[i++], a, b) : f(nums[j--], a, b);

    }

    return ans;

  }

  private int f(int x, int a, int b) {  // , int c

    return a * x * x + b * x; // + c

  }

https://leetcode.com/problems/sort-transformed-array/discuss/83317/My-easy-to-understand-Java-AC-solution-using-Two-pointers

就是三六零