有序转化数组
难度:
标签:
题目描述
代码结果
运行时间: 24 ms, 内存: 16.8 MB
/*
* LeetCode题目:有序转化数组
* 给定一个有序数组,数组中的每个元素根据一个固定公式转换,然后返回有序数组。
* 公式:f(x) = ax^2 + bx + c
* 思路:
* 1. 使用Java Stream对数组进行变换。
* 2. 使用map对每个元素应用转换公式,然后使用sorted对结果进行排序。
*/
import java.util.Arrays;
public class SortedTransformedArrayStream {
public int[] sortedTransformedArray(int[] nums, int a, int b, int c) {
return Arrays.stream(nums)
.map(x -> a * x * x + b * x + c)
.sorted()
.toArray();
}
}
解释
方法:
该题解的思路基于抛物线的性质。给定的函数 f(x) = ax² + bx + c 形成一个抛物线。当 a > 0 时,抛物线开口向上,最大值在两端;当 a < 0 时,抛物线开口向下,最小值在两端。基于此性质,可以从数组的两端开始比较,选择合适的值填充到结果数组中。如果 a > 0,从数组的最后向前填充结果数组;如果 a < 0,则从数组的开始向后填充。这种方法利用了有序数组的特性,减少了不必要的计算。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在题解中,您如何确定抛物线的最大值或最小值会出现在数组的两端而非中间?
▷🦆
当 a = 0 时,抛物线退化成直线,题解中的逻辑是否还适用,以及如何处理这种特殊情况?
▷🦆
题解中提到抛物线开口向上时,从数组末尾向前填充结果数组,这样做的具体原因是什么?
▷相关问题
有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums
,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
示例 1:
输入:nums = [-4,-1,0,3,10] 输出:[0,1,9,16,100] 解释:平方后,数组变为 [16,1,0,9,100] 排序后,数组变为 [0,1,9,16,100]
示例 2:
输入:nums = [-7,-3,2,3,11] 输出:[4,9,9,49,121]
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums
已按 非递减顺序 排序
进阶:
- 请你设计时间复杂度为
O(n)
的算法解决本问题