leetcode中等算法题（LeetCode基础算法题第85篇）

技术提高是一个循序渐进的过程，所以我讲的leetcode算法题从最简单的level开始写的，然后到中级难度，最后到hard难度全部完。

目前我选择C语言，python和Java作为实现语言，因为这三种语言还是比较典型的。由于篇幅和精力有限，其他语言的实现有兴趣的朋友请自己尝试。

初级难度说的差不多的时候，我打算再加点其他内容，我可能会从操作系统到协议栈，从分布式聊到大数据框架，从大数据聊到人工智能，... ...。

如果有任何问题可以在文章后评论或者私信给我。

我会持续分享下去，敬请您的关注。

LeetCode 977. 求有序数组的平方再排序（Squares of a Sorted Array）

问题描述：

给定一个数组已排序的非递减整型数组A，返回一个新的有序非递减数组，里面的值是A中每个元素的平方。

注：

1. 1 <= A.length <= 10000
2. -10000 <= A[i] <= 10000

示例：

C语言实现：

这里注意一个很重要的条件，数组A是有序的，但是其值的范围包含负数和非负数。那么A会存在以下三种情况：

1. 全部是非正整数，例如A=[-4, -3, -2, -1, 0],A^2=[16,9,4,1,0]；
2. 包含负整数和非负整数，例如[-3, -2, 1, 4, 5],A^2=[9,4,1,16,25]；
3. 全部是非负整数，例如[0, 1, 2, 3, 4],A^2=[0,1,4,9,16]；

我们会发现如果我们从负数和非负数的临界值这个地方将数组A分左右两块的话，左边负数的平方是逆序的，而右边的是正序的。对于这种左右有序的数组排序，我们有一种很好的办法，就是从左右两边同时排序。

代码如下：

如代码所示，我们在排序的时候同时计算左右两边值的平方，并比较，将大的放到最右边，并且适时移动左右下标的位置，直到遍历完。时间复杂度O(n)。

python语言的实现：

这题对于python来说异常简单，可以直接排序。

代码如下：

Java语言的实现：

Java的实现和C语言的实现相同。

代码如下：

,