Leetcode: Sort Transformed Array

Given a sorted array of integers nums and integer values a, b and c. Apply a 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:

nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5,

Result: [3, 9, 15, 33]

nums = [-4, -2, 2, 4], a = -1, b = 3, c = 5

Result: [-23, -5, 1, 7]

参考：https://discuss.leetcode.com/topic/48424/java-o-n-incredibly-short-yet-easy-to-understand-ac-solution

the problem seems to have many cases a>0, a=0,a<0, (when a=0, b>0, b<0). However, they can be combined into just 2 cases: a>0 or a<0

1.a>0, two ends in original array are bigger than center if you learned middle school math before.

2.a<0, center is bigger than two ends.

so use two pointers i, j and do a merge-sort like process. depending on sign of a, you may want to start from the beginning or end of the transformed array. For a==0 case, it does not matter what b's sign is.
The function is monotonically increasing or decreasing. you can start with either beginning or end.

 public class Solution {

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

         int[] res = new int[nums.length];

         int l=0, r=nums.length-1;

         int index = a<0? 0 : nums.length-1;

         while (l <= r) {

             if (a < 0) {

                 res[index++] = calc(nums[l], a, b, c)<calc(nums[r], a, b, c)? calc(nums[l++], a, b, c) : calc(nums[r--], a, b, c);

             }

             else {

                 res[index--] = calc(nums[l], a, b, c)>calc(nums[r], a, b, c)? calc(nums[l++], a, b, c) : calc(nums[r--], a, b, c);

             }

         }

         return res;

     }

     public int calc(int n, int a, int b, int c) {

         return a*n*n+b*n+c;

     }

 }

巴特西

Leetcode: Sort Transformed Array

最新文章

热门文章