SortTransformedArray [source code]

public class SortTransformedArray {
static
/******************************************************************************/
class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        if (nums.length == 0 || nums == null)
            return new int[0];
        int n = nums.length;
        int[] res = new int[n];
        if (a == 0) {
            for (int i = 0; i < n; i++) {
                int cur = b >= 0 ? nums[i] : nums[n - 1 - i];
                res[i] = b * cur + c;
            }
            return res;
        }
        //sort based on distance to pivot
        double pivot = (double) -b / (2 * a);
        int[] distSorted = new int[n];
        int lo = 0, hi = n - 1, end = n - 1;
        while (lo <= hi) {  //闭区间, 所以取等号
            double d1 = pivot - nums[lo], d2 = nums[hi] - pivot;
            if (d1 > d2) {
                distSorted[end--] = nums[lo++];
            } else {
                distSorted[end--] = nums[hi--];
            }
        }
        //populate res based on distSorted, and also a
        for (int i = 0; i < n; i++) {
            int cur = a > 0 ? distSorted[i] : distSorted[n - 1 - i];
            res[i] = a * cur * cur + b * cur + c;
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SortTransformedArray.Solution tester = new SortTransformedArray.Solution();
        int[][] inputs = {
            {-4,-2,2,4}, {1,3,5},{3,9,15,33},
            {-4,-2,2,4}, {0,3,5}, {-7,-1,11,17},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            int[] nums = inputs[3 * i];
            int[] func = inputs[1 + 3 * i];
            int a = func[0], b = func[1], c = func[2];
            int[] ans = inputs[2 + 3 * i];
            String ansStr = Printer.array(ans);
            System.out.println(Printer.separator());
            String numsStr = Printer.array(nums);
            int[] output = tester.sortTransformedArray(nums, a, b, c);
            String outputStr = Printer.array(output);
            System.out.println(
                Printer.wrapColor(numsStr + " AND " + Printer.array(func), "magenta") +
                " -> " + outputStr +
                Printer.wrapColor(", expected: " + ansStr, ansStr.equals(outputStr) ? "green" : "red")
            );
        }
    }
}

这题的笨办法当然很简单, 直接就一个一个的做, 做完了往heap里面丢, 做一个heap sort就行了, 但是这样最后的速度是NlgN, 这个是不够理想的;

大概用人逻辑思考了一下, 好像这个问题也应该不是特别难解的, Google的题目还是喜欢搞一点数学在里面的; 这个问题其实最后就是先算出来这个二次函数的中轴位置(-b/2a), 然后按照距离从近到远的顺序进行计算就行了; 有两个小问题:

• 这个按照距离排序的过程是否能够O(N)完成;
• a的正负号怎么处理;

a对应正和负的情况下, 处理是有一定的差异性, 但是应该还是能够找到一点共性在里面的, 尽量让两个程序本身上面能够写法比较一致;

无论用什么写法来写, 有一个共同的步骤, 就是要先把所有的这些数字按照距离pivot的距离进行sort, 我刚开始的想法是先把pivot在nums里面的位置用Binary Search找出来, 然后从这个位置开始向两边用2pointer来扩散; 但是后来发现这个做法不仅难写而且麻烦: 对于这个pivot用Binary Search最后找到的是hit还是miss, 要分开处理; 最关键的是, 这个Binary Search根本是没有必要的: 我们不必确定pivot在这个array里面的位置, 我们直接从两头开始, 距离从远到近来搜索就行了: 这个的好处是: 我们不做一个麻烦的Binary Search, 就无法确定最近的两个数字的位置, 但是最远的数字的位置, 我们是肯定知道的;

花了一点时间, 不过最后还是AC了; Google的题目还是套路多, 一个题目里面涉及到很多的component的组合, 而不是一个思路想通了整个题目就通关了; 最后的速度是1ms (28%), 最优解; 另外, 关于Empty Case这个东西, 真的是强调的 有点太多了;

这个是discussion最优解:

@shuxu said in 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). 2="" however,="" they="" can="" be="" combined="" into="" just="" 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 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;  
    }  
}

这个算法思路总体上跟我其实是类似的, 但是他有两个地方不同:

• 没有一个中间步骤先把nums里面的数字先按照距离sort一遍; 而是直接就往最后结果里面填;
• a等于0的情况直接整合到大于0的情况里面去了: 反正最后结果的sort就是基于一个y的比较, 直接比较就行了;

这个题目好像大部分解法都是这个类似的思路了;

Problem Description

Given a sorted array of integers nums and integer values a, b and c. Apply a function of the form f(x) = ax^2 + 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]

Credits:
Special thanks to @elmirap for adding this problem and creating all test cases.

Difficulty:Medium
Total Accepted:12.1K
Total Submissions:27.6K
Contributor: LeetCode
Companies
google
Related Topics
math two pointers