欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode算法题(数组相关)(五)——有序数组的平方

程序员文章站 2022-03-15 21:16:13
...

问题:

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

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

算法:

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

LeetCode算法题(数组相关)(五)——有序数组的平方

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

LeetCode算法题(数组相关)(五)——有序数组的平方

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

LeetCode算法题(数组相关)(五)——有序数组的平方

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

LeetCode算法题(数组相关)(五)——有序数组的平方

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

LeetCode算法题(数组相关)(五)——有序数组的平方

实现:

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

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;
    }
}

 

相关标签: leetcode刷题之路

上一篇: Linux TCP参数

下一篇: 柔性数组例子