星尘

LeetCode - 977. 有序数组的平方

发表于 更新于 分类于

977. 有序数组的平方

题目

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

示例 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]

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        size = len(nums)
        # 创建一个新数组, 用于存放计算的新值
        new_nums = [0] * size
        # 左指针
        left = 0
        # 右指针和新数组写入位置
        right, write_position = size - 1, size - 1

        # 循环终止条件是两个指针相遇
        while left <= right:
            # 最大值在右边
            if nums[right] ** 2 >= nums[left] ** 2:
                # 将平方值赋到新数组的写入位置
                new_nums[write_position] = nums[right] ** 2
                # 右边指针往前移动一位
                right -= 1
            # 最大值在左边
            else:
                # 将平方值赋到新数组的写入位置
                new_nums[write_position] = nums[left] ** 2
                # 左边指针往后移动一位
                left += 1

            # 新数组写入位置往前挪动一个
            write_position -= 1
        return new_nums
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func sortedSquares(nums []int) []int {
	size := len(nums)
	left := 0
	right := size -1
	writePosition := size -1
	newNum := make([]int, size)

	for left<= right{
		if nums[right] * nums[right] >= nums[left] * nums[left]{
			newNum[writePosition] = nums[right] * nums[right]
			right -=1
		}else {
			newNum[writePosition] = nums[left] * nums[left]
			left +=1
		}
		writePosition -=1
	}
	return newNum
}

变体

总结

技巧在于，给的数组是递增的，所以最大值一定在数组的两端，要么在最左端，要么在最右端。有因为只能找出最大值，所以新数组的插入顺序只能从大往小，也就是从后往前。

参考