LeetCode算法题（数组相关）（五）——有序数组的平方_leetcode 给定一个升序数组1,元素有重复,对每个元素算一下平方后得到新的数组2,问

问题：

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

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

算法：

看到这个题，有一个重点是数组的顺序，是非递减顺序。如果按照一个简单的思路来实现，那当然是将所有数组元素的平方，赋值给一个新的数组，之后再对新的数组进行排序。但是这样的思路做的话，题目中的非递减顺序有什么用呢？于是我写的程序利用了这个非递减顺序的条件，但是实现的过程比简单思路更复杂。下面介绍一下算法：

以这个数组为例子，将各个元素平方，有顺序变化的因素，仅仅是因为有负数。那么我们可不可以将大于等于0的数放在一边，负数放在一边。

那么现在我们可以发现，右边的部分平方以后仍然保持着顺序，但是左边的部分平方以后变成了逆序。

那么我们现在就把这个数组看成是两个数组

如果你问我为什么把16和1颠倒顺序了？我会回答，我们在写程序时把下标倒着循环不就实现了吗？好的，现在的问题就变成了，怎么把两个有序的数组，合并为一个新的有序数组。那思路就简单了，上下两个数组两两比较，较小的赋值给新数组，最后再把多余的追加到新数组的最后。以这个数组为例，合并过程如下：

实现：

奈何自己水平太次，写出这么复杂的代码，但终究是自己独立完成，凑合着看吧。

class Solution {
    public int[] sortedSquares(int[] A) {
        int len = A.length;
        int flag = 0;
        int [] B = new int[len];
        if(len == 1){
            B[0] = A[0]*A[0];
            return B;
        }
        while(A[flag]<0){
            if(flag<len-1)
                flag++;
        }
        int m = flag-1,n = flag,k=0;
        for(int i=0;i<len;i++){
            A[i] = A[i]*A[i];
        }
        while(m>=0&&n<len){
            if(A[m]<A[n])
                B[k++]=A[m--];
            else
                B[k++]=A[n++];
        }
        if(m>=0){
        	for(int q = m;q>=0;q--){
        		B[k++] = A[q];
        	}
        }
        if(n<len){
        	for(int q = n;q<len;q++){
        		B[k++] = A[q];
        	}
        }
        return B;
    }
}