LeetCode算法题(数组相关)(五)——有序数组的平方
程序员文章站
2022-03-15 21:16:13
...
问题:
给定一个按非递减顺序排序的整数数组 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;
}
}
上一篇: Linux TCP参数
下一篇: 柔性数组例子
推荐阅读
-
LeetCode算法题(数组相关)(二)——两数之和
-
LeetCode 探索 初级算法 数组 第一题:删除排序数组中的重复项
-
LeetCode 探索 初级算法 数组 第六题: 两个数组的交集 II
-
LeetCode 探索 初级算法 数组 第五题:只出现一次的数字
-
LeetCode 探索 初级算法 数组 第十题:有效的数独
-
算法--有序数组的平方(977)
-
数据结构与算法---数组、排序---部分排序、有序数组的平方
-
leetcode刷题4(寻找两个有序数组的中位数)
-
LeetCode刷题——4.寻找两个有序数组的中位数
-
LeetCode-算法题系列 (二十) => 删除排序数组中的重复项 II