返回

LeetCode 0977.有序数组的平方

有序数组的平方

LeetCode977. 有序数组的平方

题目描述

给你一个按非递减顺序排序的整数数组 nums,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。 -10^4 <= nums[i] <= 10^4

示例 1:

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

示例 2:

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

思路

题目要求

  • 给定一个含负数的升序排列的数组,
  • 返回每个数字的平方组成的新的升序数组

暴力解法:平方后排序

暴力解法没有利用题目中给到的条件:给定一个含正负数的升序数组。所以平方以后的大值肯定出现在两侧,不是左边就是右边(负数的平方为正数)

双指针法:两个指针分别指向数组的首部和尾部,每次比较两个指针所指值的大小,将大的逆序放入新数组。将双指针从外向内移动不会发生数组越界问题。

注意

因为是逆序存入数组,所以for循坏的循坏变量ilen(nums)-1开始递减。

代码

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func sortedSquares(nums []int) []int {
    length := len(nums)
    left, right := 0, length-1
    newNums := make([]int, length)
    for i := len(nums) - 1; i >= 0; i-- {
        if l, r := nums[left]*nums[left], nums[right]*nums[right]; l < r {
            newNums[i] = r
            right--
        } else {
            newNums[i] = l
            left++
        }
    }
    return newNums
}

GitHub

Built with Hugo
Theme Stack designed by Jimmy