有序数组的平方

有序数组的平方

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

示例 1：

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

Python

解一：

class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        nums_new = []
        for i in nums:
            nums_new.append(i*i)
        nums_new.sort()
        return nums_new

解二：

class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        flag = 0
        nums_new = []
        for i in nums:
            temp = i*i
            if nums_new == []:
                nums_new.append(temp)
            else:
                for i in nums_new:
                    if i >= temp:
                        nums_new.insert(nums_new.index(i),temp)
                        flag = 1
                        break
                if flag == 0:
                    nums_new.append(temp)
                flag = 0
        return nums_new

解三：

class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        result = []
        i = 0
        j = len(nums)-1
        while i <= j:
            if nums[i]*nums[i] < nums[j]*nums[j]:
                result.insert(0,nums[j]*nums[j])
                j -= 1
            else:
                result.insert(0,nums[i]*nums[i])
                i += 1
        return result

笔记

1. 解法一，先得到列表内所有元素平方之后再对其进行排序，解法二，在得到列表内每个元素的平方之后，利用直接插入排序的思路对其进行排序，最后得到已经排序的平方列表；但这两种方法时间复杂度都较高。
2. 根据题意可知，原列表内元素平方后得到的新列表中，并不是没有顺序，只是最小值在中间（原列表有负数时），最大值在两端而已，因此可以用两个指针分别指向首段和尾端，根据$(nums[i])^{{2}$和$(nums[j])}$的大小判断将哪一端先放入结果中，放入结果的端点的指针需要移动。此外需要注意循环的条件，首端指针i，末端指针j，其判断条件应为i <= j，否则会出现在最后有一个指针指向元素的平方未放入结果列表的情况。