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,

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

75. Sort Colors (Array)

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and bl

过中等难度题目.0310

  .   8  String to Integer (atoi)    13.9% Medium   . 151 Reverse Words in a String      15.7% Medium     . 288 Unique Word Abbreviation      15.8% Medium     . 29 Divide Two Integers      16.0% Medium     . 166 Fraction to Recurring Decimal      17.

[email&#160;protected] Sorting Elements of an Array by Frequency (Sort)

http://www.practice.geeksforgeeks.org/problem-page.php?pid=493 Sorting Elements of an Array by Frequency Given an array of integers, sort the array according to frequency of elements. For example, if the input array is {2, 3, 2, 4, 5, 12, 2, 3, 3, 3,

HDU 5775:Bubble Sort(树状数组)

http://acm.hdu.edu.cn/showproblem.php?pid=5775 Bubble Sort Problem Description P is a permutation of the integers from 1 to N(index starting from 1).Here is the code of Bubble Sort in C++. for(int i=1;i<=N;++i) for(int j=N,t;j>i;—j) if(P[j-1] > P