【LintCode 简单】1901. 有序数组的平方

向右看齐 2023-01-15 08:03 71阅读 0赞

1. 描述

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

2. 样例

> 输入：  
> \[-4,-1,0,3,10\]  
> 输出：  
> \[0,1,9,16,100\]

>  输入：  
> \[-7,-3,2,3,11\]  
> 输出：  
> \[4,9,9,49,121\]

3. 代码

class Solution:
        """
        @param A: The array A.
        @return: The array of the squares.
        """
        def SquareArray(self, A):
            # write your code here
            for i in range(len(A)):
                A[i] = A[i] * A[i]
            A.sort()
            return A

补充一下关于python对于sort函数的知识：

虽然python3中sort()和sorted()都可以用来排序，但二者有以下两个最主要的区别：

sort只能应用在列表**list**上，而sorted可以对**所有可迭代的对象**进行排序的操作

sort方法会在原list上直接进行排序，不会创建新的list，即没有返回值。

而sorted方法不会对原来的数据做任何改动，排序后的结果是新生成的，有返回值。

注意：如果我们不需要原来的数据而且数据是list类型，可以用sort方法，能够节省空间，否则要用sorted方法。

sort函数有两个参数可以选择，如下所示：

![20210421203459346.png][]

sort的底层实现：

Timsort是结合了合并排序（merge sort）和插入排序（insertion sort）而得出的排序算法，它在现实中有很好的效率。Tim Peters在2002年设计了该算法并在Python中使用（TimSort 是 Python 中 list.sort 的默认实现）。该算法找到数据中已经排好序的块-分区，每一个分区叫一个run，然后按规则合并这些run。Pyhton自从2.3版以来一直采用Timsort算法排序。

参考资料：

1. [https://blog.csdn.net/weixin\_43250623/article/details/88829341?utm\_medium=distribute.pc\_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-3.control&dist\_request\_id=&depth\_1-utm\_source=distribute.pc\_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-3.control][https_blog.csdn.net_weixin_43250623_article_details_88829341_utm_medium_distribute.pc_relevant.none-task-blog-2_7Edefault_7EBlogCommendFromMachineLearnPai2_7Edefault-3.control_dist_request_id_depth_1-utm_source_distribute.pc_relevant.none-task-blog-2_7Edefault_7EBlogCommendFromMachineLearnPai2_7Edefault-3.control]

2. [https://www.cnblogs.com/clement-jiao/p/9243066.html][https_www.cnblogs.com_clement-jiao_p_9243066.html]

[20210421203459346.png]: /images/20221022/ab51bcbaf4764de5970483c72b436097.png
[https_blog.csdn.net_weixin_43250623_article_details_88829341_utm_medium_distribute.pc_relevant.none-task-blog-2_7Edefault_7EBlogCommendFromMachineLearnPai2_7Edefault-3.control_dist_request_id_depth_1-utm_source_distribute.pc_relevant.none-task-blog-2_7Edefault_7EBlogCommendFromMachineLearnPai2_7Edefault-3.control]: https://blog.csdn.net/weixin_43250623/article/details/88829341?utm_medium=distribute.pc_relevant.none-task-blog-2~default~BlogCommendFromMachineLearnPai2~default-3.control&dist_request_id=&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~BlogCommendFromMachineLearnPai2~default-3.control
[https_www.cnblogs.com_clement-jiao_p_9243066.html]: https://www.cnblogs.com/clement-jiao/p/9243066.html