977. 有序数组的平方
给定一个按非递减顺序排序的整数数组A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。
示例 1:
输入:[-4,-1,0,3,10]
输出:[0,1,9,16,100]
示例 2:
输入:[-7,-3,2,3,11]
输出:[4,9,9,49,121]
提示:
1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非递减顺序排序。
思路:其实只要做乘方之后的排序就能做出来,但是复杂度是在n^2,考虑能不能在O(n)中解出来,我的想法是,找到了数组中中间两个数的位置,也就是第一个正数和第一个负数的位置,然后通过位置的比较,来改变索引,其实我的思路是对的,用两个索引去表示位置,但是好像考虑情况比较多,数组全是正数,或者全是负数,或者正多负少,或者正少负多,最初来运行也不是很快,需要改善
1 | public class Solution_977 { |
别的思路,我看了下,其实索引位置可以定在开头和结尾,那么判断条件就是当他们两个相等时就可以终止循环了(为什么我没有想到!!!别问,问就是我菜!)
1 | class Solution { |