数组03-有序数组的平方

Posted on Edited on

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

暴力解法是把数组的每个元素取平方后，用各种排序算法来排序 时间复杂度为O(nlogn) 双指针可以直接把时间复杂度降到O(n)

简单点说就是两个指针 一头一尾 同时向中间靠拢 逐个比较元素的大小 然后放到新的数组里面去 因为平方的特殊性 最大值一定是出现在数组的两端的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        slow=0
        fast=len(nums)-1
        ans=[float('inf')]*len(nums)
        k=len(nums)-1
        while slow != fast:
            if nums[slow]*nums[slow]<nums[fast]*nums[fast]:
                ans[k]=nums[fast]*nums[fast]
                fast-=1
                k-=1
            else:
                ans[k]=nums[slow]*nums[slow]
                slow+=1
                k-=1
        ans[0]=nums[slow]*nums[slow]
        return ans

相比这道题本身的算法 我觉得还一个注意的是python创建定长数组的方法

1
nums=[float('inf')]*100  # 创建一个长度为100  元素都是无穷大的数组