LC: 360. Sort Transformed Array
https://leetcode.com/problems/sort-transformed-array/
360. Sort Transformed Array
Given a sorted integer array nums and three integers a, b and c, apply a quadratic function of the form f(x) = ax2 + bx + c to each element nums[i] in the array, and return the array in a sorted order.
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]Constraints:
1 <= nums.length <= 200-100 <= nums[i], a, b, c <= 100numsis sorted in ascending order.
Follow up: Could you solve it in O(n) time?
The Essence:
Wenn eine bestimmte Menge sortierter Punkte mit einer quadratischen Funktion abgebildet wird, haben die Werte ganz links bzw. ganz rechts den größten absoluten Wert:
Daher kommen die letzten Werte im sortierten Array zuerst aus den Indizes an Rändern, bis sich diese Indizes in der Mitte treffen, wo sie den Wert für das erste Element des aufsteigend sortierten Arrays ergeben. Wenn der Parameter a negativ ist, ist die Parabel nach unten geöffnet. Deswegen entsprechen in diesem Fall die Randwerte den Anfang des sortierten Arrays.
Details
Man verwendet zwei Zeiger für den Anfang und das Ende des Arrays und rechnet die Funktionswerte. Danach verschiebt man die eiger dementsprechend.
Solution(s) and Further Explanation:
More detailed information and code can be found here:
Default Code:
Last updated