977.有序数组的平方

题目详情

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

  1. 输入：nums = [-4,-1,0,3,10]
  2. 输出：[0,1,9,16,100]
  3. 解释：平方后，数组变为 [16,1,0,9,100]
  4. 排序后，数组变为 [0,1,9,16,100]

示例 2：

  1. 输入：nums = [-7,-3,2,3,11]
  2. 输出：[4,9,9,49,121]

提示：

  • <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 已按 非递减顺序 排序

进阶：

请你设计时间复杂度为 O(n) 的算法解决本问题

解法

思路

  1. 双指针，i指向起始位置，j指向终止位置
  2. 定义一个新的数组result，大小和nums一样，设置一个k指向result终止位置
  3. 如果nums[i]*nums[i] < nums[j]*nums[j]，那么 result[k] = nums[j]*nums[j]
  4. 如果nums[i]*nums[i] >= nums[j]*nums[j]，那么 result[k] = nums[i]*nums[i]

实现

  1. Java
  1. public int[] sortedSquares(int[] nums) {
  2.     int i = 0;
  3.     int j = nums.length - 1;
  4.     int k = nums.length - 1;
  5.     int[] result = new int[nums.length];
  6.     while (i <= j) {
  7.         int im = nums[i] * nums[i];
  8.         int jm = nums[j] * nums[j];
  9.         if (im < jm) {
  10.             result[k] = jm;
  11.             j--;
  12.         } else {
  13.             result[k] = im;
  14.             i++;
  15.         }
  16.         k--;
  17.     }
  18.     return result;
  19. }
  1. Python3
def sortedSquares(self, nums: List[int]) -> List[int]:
    i, j, k = 0, len(nums) - 1, len(nums) - 1
    result = [None] * len(nums)
    while i <= j:
        im = nums[i] ** 2
        jm = nums[j] ** 2
        if im < jm:
            result[k] = jm
            j -= 1
        else:
            result[k] = im
            i += 1
        k -= 1
    return result
  1. Go
func sortedSquares(nums []int) []int {
    i, j, k := 0, len(nums)-1, len(nums)-1
    result := make([]int, len(nums))
    for i <= j {
        im, jm := nums[i]*nums[i], nums[j]*nums[j]
        if im < jm {
            result[k] = jm
            j--
        } else {
            result[k] = im
            i++
        }
        k--
    }
    return result
}