leetcode
leetcode 301 ~ 350
有序转化数组

有序转化数组

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
在题解中,您如何确定抛物线的最大值或最小值会出现在数组的两端而非中间?
抛物线的性质决定了其最值的位置。对于给定的抛物线函数 f(x) = ax² + bx + c,其顶点的 x 坐标由公式 -b/(2a) 给出。当 a > 0 时,抛物线开口向上,其两端值逐渐增大,因而最大值出现在左端或右端;当 a < 0 时,抛物线开口向下,其两端值逐渐减小,因而最小值出现在左端或右端。由于题目中的数组是有序的,这意味着可以直接通过比较数组端点的函数值来确定填充顺序,实现高效的排序。
🦆
当 a = 0 时,抛物线退化成直线,题解中的逻辑是否还适用,以及如何处理这种特殊情况?
当 a = 0 时,函数 f(x) = ax² + bx + c 简化为 f(x) = bx + c,这是一个线性函数。在这种情况下,若 b > 0,则函数值随 x 增大而增大;若 b < 0,则函数值随 x 增大而减小。因此,可以简单地按照 b 的符号来决定填充结果数组的顺序:如果 b >= 0,从数组的开始向后填充;如果 b < 0,则从数组的末尾向前填充。这保持了算法的一致性和高效性。
🦆
题解中提到抛物线开口向上时,从数组末尾向前填充结果数组,这样做的具体原因是什么?
当抛物线开口向上(a > 0)时,函数值在数组的两端较高,且随着 x 值向中间靠拢而减小。因此,为了建立一个从大到小的有序数组,需要从结果数组的末尾开始填充较大的值。这样,可以确保在比较两端的函数值时,总是将较大的值放在结果数组的后端,然后逐步向数组的前端移动,从而保持数组的有序性。

相关问题

有序数组的平方

给你一个按 非递减顺序 排序的整数数组 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) 的算法解决本问题