360.Sort Transformed Array

Tags: [two_pointer], [merge], [trick], [math]

Com: {g}

Link: https://leetcode.com/problems/sort-transformed-array/#/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]

Better Solution: Two Pointer, Merge, Math

class Solution(object):
    def sortTransformedArray(self, nums, a, b, c):
        """
        :type nums: List[int]
        :type a: int
        :type b: int
        :type c: int
        :rtype: List[int]
        """
        if not nums:
            return []

        size = len(nums)
        nums = map(lambda x: a*x**2 + b*x + c, nums)
        rest = [0 for _ in xrange(size)]
        index = 0 if a < 0 else size - 1

        l = 0
        r = size - 1
        while l <= r:
            if a >= 0:
                if nums[l] >= nums[r]:
                    rest[index] = nums[l]
                    l += 1
                else:
                    rest[index] = nums[r]
                    r -= 1
                index -= 1
            else:
                if nums[l] <= nums[r]:
                    rest[index] = nums[l]
                    l += 1
                else:
                    rest[index] = nums[r]
                    r -= 1
                index += 1

        return rest

Revelation:

• If a > 0, 曲线开口向上，两边的值比中间的大，所以我们倒着填充rest，每次填充时选大的值.
• if a < 0, 曲线开口向下，两边的值比中间的小，所以我们正着填充rest，每次填充时选小的值.
• if a == 0, 是一条单调的直线，正着填充rest和倒着填充rest都一样，正着填充就每次选小的，倒着填充就每次选大的，所以我们可以把a == 0的情况归于a > 0 或 a < 0.
• 以为曲线要么是两边高中间低，要么是两边低中间高，要么‘无所谓’，所以从两边往中间扫描nums是个好策略.

Solution: Two Pointer, Merge, Math

class Solution(object):
    def sortTransformedArray(self, nums, a, b, c):
        """
        :type nums: List[int]
        :type a: int
        :type b: int
        :type c: int
        :rtype: List[int]
        """
        if not nums:
            return []
        nums = map(lambda x: a*(x**2) + b*x + c, nums)
        size = len(nums)

        ascending = None
        index = 0
        while index < size - 1:
            if ascending is None and nums[index] != nums[index + 1]:
                ascending = True if nums[index] < nums[index + 1] else False

            elif ascending is True and nums[index] > nums[index + 1]:
                break

            elif ascending is False and nums[index] < nums[index + 1]:
                break

            index += 1

        if index == size - 1:
            if ascending is False:
                nums.reverse()
            return nums

        left = nums[:index]
        right = nums[index:]
        if ascending:
            right.reverse()
        else:
            left.reverse()

        l = 0
        r = 0
        i = 0
        while l < len(left) and r < len(right):
            if left[l] <= right[r]:
                nums[i] = left[l]
                l += 1
                i += 1
            else:
                nums[i] = right[r]
                r += 1
                i += 1

        while l < len(left):
            nums[i] = left[l]
            l += 1
            i += 1
        while r < len(right):
            nums[i] = right[r]
            r += 1
            i += 1

        return nums

Revelation:

• Because the a*x^2 + b*x + c is a second degree polynomial (二次多项式), after apply the formula, the data should be like the following pics:
• So after apply the formula, there are four cases:
• (1) the data has been sorted, the order is ascending.
• (2) the data has been sorted, the order is descending.
• (3) the left part of data is sorted, the order is ascending, and the right part of data is sorted, the order is descending.
• (4) the left part of data is sorted, the order is descending, and the right part of data is sorted, the order is ascending.

Note:

• Time complexity = O(n), n is the number of elements in the given array.