Thursday, September 27, 2018

360. Sort Transformed Array

360Sort Transformed Array
Given a sorted array of integers nums and integer values ab 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]
---------------------
一元二次方程
咋看之下有4种情况 a > 0, a < 0, a == 0 && b > 0, a ==0 && b < 0, 其实代码一整合就只有2种:a >= 0和a < 0

class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int[] rt = new int[n];
        int left = 0, right = n - 1;
        int itr = a >= 0 ? n - 1 : 0;
        
        while (left <= right) {
            if (a >= 0) {
                if (f(nums[left], a, b, c) > f(nums[right], a, b, c)) {
                    rt[itr] = f(nums[left], a, b, c);
                    left++;
                }else {
                     rt[itr] = f(nums[right], a, b, c);
                    right--;
                }          
                itr--;
            }else {
                if (f(nums[left], a, b, c) < f(nums[right], a, b, c)) {
                    rt[itr] = f(nums[left], a, b, c);
                    left++;
                }else {
                     rt[itr] = f(nums[right], a, b, c);
                    right--;
                }          
                itr++;
            }
        }
        
        return rt;
    }
    
    private int f(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
}

No comments:

Post a Comment