[LeetCode] Sort Transformed Array 变换数组排序 - Grandyang - 博客园
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]
Credits:
Special thanks to @elmirap for adding this problem and creating all test cases.
这道题给了我们一个数组,又给了我们一个抛物线的三个系数,让我们求带入抛物线方程后求出的数组成的有序数组。那么我们首先来看O(nlgn)的解法,这个解法没啥可说的,就是每个算出来再排序,这里我们用了最小堆来帮助我们排序,参见代码如下:
Read full article from [LeetCode] Sort Transformed Array 变换数组排序 - Grandyang - 博客园
No comments:
Post a Comment