Leetcode 977. Squares of a Sorted Array

冷不防 2022-09-05 14:51 144阅读 0赞

文章作者：Tyan
博客：noahsnail.com | CSDN | 简书

1. Description

Squares of a Sorted Array

2. Solution

**解析：**Version 1，采用双指针，先计算平方和，再比较大小，较大的更新到结果数组中。Version 2先比较二者绝对值大小，再将平方更新到结果中。

  • Version 1

    class Solution:

    1. def sortedSquares(self, nums: List[int]) -> List[int]:
    2.     n = len(nums)
    3.     i = 0
    4.     j = n - 1
    5.     result = [0] * n
    6.     index = n - 1
    7.     x = nums[i] ** 2
    8.     y = nums[j] ** 2
    9.     while i <= j:    
    10.         if x <= y:
    11.             result[index] = y
    12.             index -= 1
    13.             j -= 1
    14.             y = nums[j] ** 2
    15.         else:
    16.             result[index] = x
    17.             index -= 1
    18.             i += 1
    19.             x = nums[i] ** 2
    20.     return result

  • Version 2

    class Solution:

    1. def sortedSquares(self, nums: List[int]) -> List[int]:
    2.     n = len(nums)
    3.     i = 0
    4.     j = n - 1
    5.     result = [0] * n
    6.     index = n - 1
    7.     while i <= j: 
    8.         x = nums[i]
    9.         y = nums[j]
    10.         if abs(x) <= abs(y):
    11.             result[index] = y * y
    12.             index -= 1
    13.             j -= 1
    14.             y = nums[j]
    15.         else:
    16.             result[index] = x * x
    17.             index -= 1
    18.             i += 1
    19.             x = nums[i]
    20.     return result

Reference

  1. https://leetcode.com/problems/squares-of-a-sorted-array/

发表评论

表情：
评论列表 （有 0 条评论，144人围观）

还没有评论，来说两句吧...

相关阅读

    相关 LeetCode：Median of Two Sorted Arrays

    第四题是找两个已经排序的数组的中位数，其实就是寻找两个排序数组的第k个数。寻找第k个数就需要把k均分到两个数组，可以用到结论如果a\[k/2-1\]小雨b\[k/2-1\]，那

    悠悠悠悠/ 0 赞/ 253 阅读