LeetCode 360. 有序转化数组

Categories:

题目描述
思路分析
1. 解法一：双指针（推荐）
相似题目

题目描述

✅ 360. 有序转化数组

思路分析

解法一：双指针（推荐）

核心思路：

二次函数 f(x) = ax² + bx + c 开口方向由 a 决定：a > 0 时两端大中间小，a < 0 时两端小中间大

对已排序数组用双指针从两端向中间收缩，每次取较大（a > 0）或较小（a < 0）的值填入结果数组

a == 0 时退化为线性函数，同样适用双指针从任意方向处理

利用有序性避免排序，直接 O(n) 构造有序结果

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度，双指针各遍历一次

空间复杂度：O(1)，不计输出数组的额外空间

class Solution {

  public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
    int n = nums.length;
    int[] result = new int[n];

    int left = 0;
    int right = n - 1;

    // a > 0 时两端值大，从后往前填；a <= 0 时两端值小，从前往后填
    int index = (a >= 0) ? n - 1 : 0;

    while (left <= right) {
      int leftVal = applyFunc(nums[left], a, b, c);
      int rightVal = applyFunc(nums[right], a, b, c);

      if (a >= 0) {
        // 两端大，取较大值放到结果末尾
        if (leftVal >= rightVal) {
          result[index--] = leftVal;
          left++;
        } else {
          result[index--] = rightVal;
          right--;
        }
      } else {
        // 两端小，取较小值放到结果开头
        if (leftVal <= rightVal) {
          result[index++] = leftVal;
          left++;
        } else {
          result[index++] = rightVal;
          right--;
        }
      }
    }

    return result;
  }

  private int applyFunc(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 {
    n := len(nums)
    result := make([]int, n)

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

    left, right := 0, n-1

    // a >= 0 时从后往前填较大值；a < 0 时从前往后填较小值
    index := n - 1
    if a < 0 {
        index = 0
    }

    for left <= right {
        leftVal := applyFunc(nums[left])
        rightVal := applyFunc(nums[right])

        if a >= 0 {
            // 取较大值放末尾
            if leftVal >= rightVal {
                result[index] = leftVal
                left++
            } else {
                result[index] = rightVal
                right--
            }
            index--
        } else {
            // 取较小值放开头
            if leftVal <= rightVal {
                result[index] = leftVal
                left++
            } else {
                result[index] = rightVal
                right--
            }
            index++
        }
    }

    return result
}

相似题目

题目	难度	考察点
977. 有序数组的平方	简单	双指针、数组
88. 合并两个有序数组	简单	双指针、数组
167. 两数之和 II - 输入有序数组	中等	双指针、二分查找
75. 颜色分类	中等	双指针、排序
611. 有效三角形的个数	中等	双指针、排序

本文作者: HGNULB

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