Java O(N) easy, verbose, explained, picture, with math recap


  • 0

    Code:

    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;
        }
    }
    

    And the picture:

    The process consists of two procedures:

    1. sort all numbers (xs) by their distance to the pivot;
    2. populate the result array (ys).

    The code should be easy to understand with the idea explained by the picture.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.