LeetCode刷题977-简单-有序数组的平方


LeetCode刷题977-简单-有序数组的平方

文章目录


前言

算法作为极其重要的一点,是大学生毕业找工作的核心竞争力,所以为了不落后与人,开始刷力扣算法题!

第一遍,不求最优解,但求能过!!!

???? :❤布小禅❤

???? 作者专栏:

❤Python❤

❤Java❤

这是我刷第 9/100 道力扣简单题


一、题目描述

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

提示:

1 <= nums.length <= 104

-104 <= nums[i] <= 104

nums 已按 非递减顺序 排序

进阶:

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


二、实例

示例 1:

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

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


三、解题思路

  1. 使用内置函数法
    遍历,平方,比较,排序
    排序可以使用内置函数sqrt()
  2. 双指针法
    因为原来的数组/列表是有序的,只不过需要平方,然后再排序,所以可以使用双指针法
    类似于二分查找那种方法
    我们需要两个数分别来记录数组/列表左边和右边
    然后比较左边和右边的大小,将大的添加进一个数组/列表
    最后这个数组/列表就是我们的答案


四、代码

  1. 内置函数法
    时间复杂度:O(n)
    空间复杂度:O(1)
from typing import List

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        ans = []
        for i in nums:
            ans.append(i**2)
        return sorted(ans)
  1. 双指针法
    时间复杂度:O(n)
    空间复杂度:O(1)
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        ans = []
        n = len(nums)
        m = 0
        while m <= n-1:
            i = nums[m]*nums[m]
            j = nums[n-1]*nums[n-1]
            if i >= j:
                ans.append(i)
                m += 1
            else:
                ans.append(j)
                n -= 1
        return ans[::-1]


结语

坚持最重要,每日一题必不可少!

LeetCode刷题977-简单-有序数组的平方

上一篇:[CareerCup] 11.3 Search in Rotated Sorted Array 在旋转有序矩阵中搜索


下一篇:美*系统漏洞存13年 提前释放服刑者3000多人