首页 > 代码库 > Sort Transformed Array
Sort Transformed Array
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]
分析:
抛物线的中轴线可以通过-b/2a来计算,这题可以转换成按照各个点到中轴线的距离依次排列。所以,我们先找到距离中轴线最近的点 p ,然后,设置两个pointer,从p开始,一个向左走,一个向右走。看两个Pointer对应的值哪个离中轴线更近,然后取近的一个,同时移动对应的pointer.
后来发现有更好的方法,也是使用两个pointer,一个指向最左边,一个指向最右边。然后谁离中轴线越远,就选谁。
https://discuss.leetcode.com/topic/48424/java-o-n-incredibly-short-yet-easy-to-understand-ac-solution
1 public class Solution { 2 public int[] sortTransformedArray(int[] nums, int a, int b, int c) { 3 int n = nums.length; 4 int[] sorted = new int[n]; 5 int i = 0, j = n - 1; 6 int index = a >= 0 ? n - 1 : 0; 7 while (i <= j) { 8 if (a >= 0) { 9 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); 10 } else { 11 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); 12 } 13 } 14 return sorted; 15 } 16 17 private int quad(int x, int a, int b, int c) { 18 return a * x * x + b * x + c; 19 } 20 }
Sort Transformed Array
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。