LeetCode 360. 有序转化数组

2022-03-07 HGNULB 约 5 分钟

文章信息 7 个分类 4 个标签

分类

LeetCode CodeTop 中等未解决会员题 1-2 字节

题目描述

✅ 360. 有序转化数组

题意分析

输入数组 nums 已经有序，将每个元素代入 $f(x)=ax^2+bx+c$，再按非递减顺序返回所有函数值。二次变换可能改变原有大小关系，不能直接按输入顺序输出；要做到线性时间，需要利用函数形状。

解法：端点双指针

核心思路

[!blue]

用 left、right 指向剩余输入区间的两端。数组有序，因此中间所有输入值都位于这两个端点值之间。二次函数开口的方向决定了这个区间上的哪一种极值一定出现在端点。

a > 0 时，抛物线开口向上，函数在顶点两侧分别下降、上升。区间内的最高值只能来自某个端点，所以比较 f(nums[left]) 与 f(nums[right])，取较大者。这是所有剩余值中最大的一个，应写入结果的最后一个空位，写指针向左移动。

a < 0 时，抛物线开口向下，内部可能更高，而最低值一定来自端点。每次取两个端点函数值中较小者，写入结果的第一个空位，写指针向右移动。

选走哪一端，就只移动该端的输入指针。剩余元素仍是原有序数组的连续区间，端点极值性质继续成立。因此每轮写入的都是当前应放在结果边界的值，直到所有元素写完，结果整体有序。

a = 0 时退化为线性函数：b 为正、负或零时，函数分别递增、递减或恒定，最大值仍在端点。因此可以直接沿用 a >= 0 的“取最大、从后写”分支，不需要计算对称轴或额外拆分情况。

当两个端点函数值相等时，取任意一端都可以，但本轮只消耗一个输入元素，另一份相同值仍要保留。left == right 时也还剩一个元素，所以循环条件必须包含等号；每轮区间长度减少一，最终自然结束。

解题步骤

初始化左右指针和结果写入位置。

计算两端函数值。

按 a 的符号选择极值，写入对应结果端。

移动被选中的输入指针与输出位置。

代码实现

class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int[] answer = new int[nums.length];
        int left = 0;
        int right = nums.length - 1;
        // 开口向上从结果末尾填最大值，开口向下从开头填最小值。
        int write = a >= 0 ? nums.length - 1 : 0;

        while (left <= right) {
            int leftValue = transform(nums[left], a, b, c);
            int rightValue = transform(nums[right], a, b, c);

            if (a >= 0) {
                // 当前剩余最大值在两端，取出后收缩对应一侧。
                if (leftValue >= rightValue) {
                    answer[write--] = leftValue;
                    left++;
                } else {
                    answer[write--] = rightValue;
                    right--;
                }
            } else {
                if (leftValue <= rightValue) {
                    answer[write++] = leftValue;
                    left++;
                } else {
                    answer[write++] = rightValue;
                    right--;
                }
            }
        }

        return answer;
    }

    private int transform(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
}

func sortTransformedArray(nums []int, a int, b int, c int) []int {
    answer := make([]int, len(nums))
    left, right := 0, len(nums)-1
    // 开口向上从结果末尾填最大值，开口向下从开头填最小值。
    write := 0
    if a >= 0 {
        write = len(nums) - 1
    }

    transform := func(x int) int {
        return a*x*x + b*x + c
    }

    for left <= right {
        leftValue := transform(nums[left])
        rightValue := transform(nums[right])

        if a >= 0 {
            // 当前剩余最大值在两端，取出后收缩对应一侧。
            if leftValue >= rightValue {
                answer[write] = leftValue
                left++
            } else {
                answer[write] = rightValue
                right--
            }
            write--
        } else {
            if leftValue <= rightValue {
                answer[write] = leftValue
                left++
            } else {
                answer[write] = rightValue
                right--
            }
            write++
        }
    }
    return answer
}

复杂度分析

时间复杂度：$O(n)$，每轮消耗一个输入元素。

空间复杂度：辅助空间 $O(1)$，返回数组占 $O(n)$。

关键点总结

[!green]

开口方向决定取最大还是最小，也决定写入方向。

无需计算对称轴，比较端点即可。

两指针相遇时仍有一个元素要处理。

易错点总结

[!yellow]

取最大值却从前向后写：结果会降序。

a<0 仍取端点最大值：区间最大值可能位于内部。

循环排除指针相等：漏掉最后一项。

两端值相等时不移动指针：循环不能推进。

相似题目

题目	难度	关联与区别
977. 有序数组的平方	简单	平方是二次函数的特例，利用两端极值从输出末尾合并，本题还要按二次项符号确定方向。
88. 合并两个有序数组	简单	同样合并两个有序来源，二次函数变换后可将两侧单调段视为两条有序序列。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/35911216

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！