Sort Transformed Array

Given a sorted array of integers nums and integer values ab 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 }
时间: 11-18

Sort Transformed Array的相关文章

360. 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,

[LeetCode] 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,

Leetcode 360: Sort Transformed Array

Given a sorted array of integers nums and integer values a, b and c. Apply a quadratic 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 =

360. Sort Transformed Array二元一次方程返回大数序列

[抄题]: Given a sorted array of integers nums and integer values a, b and c. Apply a quadratic 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 1

leetcode360 - Sort Transformed Array - medium

Given a sorted array of integers nums and integer values a, b and c. Apply a quadratic 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 1:Input: n

Sort the Array

Being a programmer, you like arrays a lot. For your birthday, your friends have given you an array a consisting of n distinct integers. Unfortunately, the size of a is too small. You want a bigger array! Your friends agree to give you a bigger array,

Codeforces Round #258 (Div. 2) B. Sort the Array

Being a programmer, you like arrays a lot. For your birthday, your friends have given you an array a consisting of n distinct integers. Unfortunately, the size of a is too small. You want a bigger array! Your friends agree to give you a bigger array,

Codeforces Round #258 (Div. 2) B. Sort the Array(简单题)

题目链接:http://codeforces.com/contest/451/problem/B ---------------------------------------------------------------------------------------------------------------------------------------------------------- 欢迎光临天资小屋:http://user.qzone.qq.com/593830943/ma

(周日赛)Sort the Array

题意:一段数字,逆置其中两个使其递增 DescriptionBeing a programmer, you like arrays a lot. For your birthday, your friends have given you an array a consisting of ndistinct integers. Unfortunately, the size of a is too small. You want a bigger array! Your friends agre