class Solution {
public:
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
}
};
360. 有序转化数组
给你一个已经 排好序 的整数数组 nums 和整数 a 、 b 、 c 。对于数组中的每一个元素 nums[i] ，计算函数值 f(x) = ax2 + bx + c ，请 按升序返回数组 。
示例 1：
输入: nums = [-4,-2,2,4], a = 1, b = 3, c = 5 输出: [3,9,15,33]
示例 2：
输入: nums = [-4,-2,2,4], a = -1, b = 3, c = 5 输出: [-23,-5,1,7]
提示：
1 <= nums.length <= 200-100 <= nums[i], a, b, c <= 100nums 按照 升序排列
进阶：你可以在时间复杂度为 O(n) 的情况下解决这个问题吗？
相似题目
原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.6 MB, 提交时间: 2023-10-22 09:37:01
func sortTransformedArray(nums []int, a int, b int, c int) []int {
l := len(nums)
res := make([]int, l)
if a == 0{
for i, v := range nums{
res[i] = calc(v,a,b,c)
}
if b < 0{
reverse(res)
}
} else {
//根据抛物线顶点公式计算mid
mid := -1*float32(b)/2/float32(a)
idx := l-1
left, right := 0, l-1
for left <= right{
// 这里其实是比较讨巧的一个代码，实际上mid，nums[left],nums[right]有三种情况（按从小到大递增）
// mid，nums[left],nums[right]
// nums[left], mid,nums[right]
// nums[left],nums[right], mid
//但是这里一行代码把所有情况都给总结了。证明就用枚举法证明，不赘述了。
if mid - float32(nums[left]) <= float32(nums[right]) - mid {
res[idx] = calc(nums[right], a,b,c)
right--
} else {
res[idx] = calc( nums[left], a,b,c)
left++
}
idx--
}
if a < 0 {
reverse(res)
}
}
return res
}
func calc(v, a,b,c int) int {
return a *v*v+b*v+c
}
func reverse(nums []int){
l := len(nums)
for i:=0; i<l/2;i++{
nums[i], nums[l-1-i] = nums[l-1-i], nums[i]
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 2.6 MB, 提交时间: 2023-10-22 09:36:32
func sortTransformedArray(nums []int, a int, b int, c int) []int {
n := len(nums)
if n == 0 {
return nil
}
var ans = make([]int, n)
idx := n-1
if a == 0 {
for i := n-1; i >= 0; i-- {
ans[idx] = fx(nums[i], a, b, c)
idx--
}
if b < 0 {
reverse(ans)
}
return ans
}
mid := -1*float32(b)/2/float32(a)
left, right := 0, len(nums) - 1
for left <= right {
if mid - float32(nums[left]) >= float32(nums[right]) - mid {
ans[idx] = fx(nums[left], a, b, c)
left++
} else {
ans[idx] = fx(nums[right], a, b, c)
right--
}
idx--
}
if a < 0 {
reverse(ans)
}
return ans
}
func fx(x int, a int, b int, c int) int {
return a * x * x + b * x + c
}
func reverse(nums []int) {
n := len(nums)
for i:=0; i < n / 2; i++ {
nums[i], nums[n-1-i] = nums[n-1-i], nums[i]
}
}
python3 解法, 执行用时: 2524 ms, 内存消耗: 26.9 MB, 提交时间: 2023-10-22 09:36:02
class Solution:
def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:
tmp = [a*(x**2)+b*x+c for x in nums]
return self.bucket_sort(tmp)
######### 桶排序 时间复杂度O(n),空间复杂度O(n) #######
def bucket_sort(self, nums: List[int]) -> List[int]:
minnum = min(nums)
maxnum = max(nums)
len_a = max(0, maxnum) + 1
len_b = (-minnum if minnum < 0 else 0) + 1
a = [0 for _ in range(len_a)] #0+正数
b = [0 for _ in range(len_b)] #负数
for x in nums:
if x >= 0:
a[x] += 1
else:
b[-x] += 1
res = []
for x in range(len(b)-1, 0, -1):
if b[x] > 0:
res += [-x]*b[x]
for x in range(len(a)):
if a[x] > 0:
res += [x]*a[x]
return res
# 数学公式
def sortTransformedArray2(self, nums: List[int], a: int, b: int, c: int) -> List[int]:
return sorted( [a*(x**2)+b*x+c for x in nums] )
def sortTransformedArray3(self, nums: List[int], a: int, b: int, c: int) -> List[int]:
########### 抛物线判断开口。然后判断与对称轴的距离(直接计算结果也行) ###############
########## 计算函数值 ##########
def f(x: int) -> int:
return a * (x**2) + b * x + c
if not nums:
return []
n = len(nums)
res = [0 for _ in range(n)]
################ 双指针，从外侧向中心“夹逼”的思想
L, R = 0, n-1
###### 抛物线开口向上，或者a==0一条直线（直线合并在哪种情况都行）
if a >= 0:
idx = n-1 #越外侧的越大
while L <= R:
if f(nums[L]) > f(nums[R]):
res[idx] = f(nums[L])
L += 1
else:
res[idx] = f(nums[R])
R -= 1
idx -= 1
###### 抛物线开口向下
else:
idx = 0 #越外侧的越小
while L <= R:
if f(nums[L]) < f(nums[R]):
res[idx] = f(nums[L])
L += 1
else:
res[idx] = f(nums[R])
R -= 1
idx += 1
############ 返回结果
return res
java 解法, 执行用时: 0 ms, 内存消耗: 40.8 MB, 提交时间: 2023-10-22 09:34:23
class Solution {
private int cal(int x, int a, int b, int c) {
return a * x * x + b * x + c;
}
/**
* 首先了解抛物线概念,https://baike.baidu.com/item/%E6%8A%9B%E7%89%A9%E7%BA%BF%E6%96%B9%E7%A8%8B/2021428
* 极点概念:的https://baike.baidu.com/item/%E6%9E%81%E5%80%BC%E7%82%B9
* 首先根据 a = 0, bx + c是一条直线 学名斜截式概念: https://baike.baidu.com/item/%E6%96%9C%E6%88%AA%E5%BC%8F
* b是斜率, 斜率大于零则x值越大y也越大, 斜率小于0则x越大,y值越小.
* 如果是抛物线则必然存在一个极点(极大值/极小值), 极点就是导数为0的点, f(x)导数: 2ax+b = 0 ==> x = -b/2a
* a > 0, 则抛物线是一条向上的抛物线,存在极小值, x坐标点到极点的绝对值越小则f(x) 越小,反则反之.
* a < 0, 则抛物线是一条向下的抛物线,存在极大值, x坐标点到极点的绝对值越小则f(x) 越大,反则反之.
* @param nums
* @param a
* @param b
* @param c
* @return
*/
public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
int[] temp = new int[nums.length];
if (a == 0) {
if (b == 0)
Arrays.fill(temp, c);
for (int i = 0; i < nums.length; i++) {
if (b > 0)
temp[i] = b * nums[i] + c;
else
temp[nums.length - 1 - i] = b * nums[i] + c;
}
return temp;
}
int index = 0;
double mid = -b * 1.0 / a / 2;
int l = 0, r = nums.length - 1;
if (a > 0) {
index = nums.length - 1;
while (l <= r) {
if (Math.abs(mid - nums[l]) > Math.abs(mid - nums[r]))
// 最大值
temp[index] = cal(nums[l++], a, b, c);
else
temp[index] = cal(nums[r--], a, b, c);
index--;
}
} else {
while (l <= r) {
if (Math.abs(mid - nums[l]) > Math.abs(mid - nums[r]))
// 最小值
temp[index++] = cal(nums[l++], a, b, c);
else
temp[index++] = cal(nums[r--], a, b, c);
}
}
return temp;
}
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 9.4 MB, 提交时间: 2023-10-22 09:33:58
// O(NlgN)
class Solution1 {
public:
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
vector<int> res;
for (const auto& x : nums) {
int t = a * x * x + b * x + c;
res.push_back(t);
}
sort(res.begin(), res.end());
return res;
}
};
// O(N)
class Solution {
public:
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
if (nums.empty()) {
return {};
}
int N = nums.size();
vector<int> res(N, 0);
auto fx = [&](const auto& x) {
return a * x * x + b * x + c;
};
int i = 0;
int j = N - 1;
int index = a >= 0 ? N - 1 : 0; // a > 0, backward, a < 0, forward
while (i <= j) {
if (a >= 0) { //向上的抛物线,合并a=0为直线，单调增减情况到a>0（合并到a < 0也行）
res[index--] = fx(nums[i]) >= fx(nums[j]) ? fx(nums[i++]) : fx(nums[j--]);
} else { // (a < 0)
res[index++] = fx(nums[i]) > fx(nums[j]) ? fx(nums[j--]) : fx(nums[i++]);
}
}
return res;
}
};