有序数组的平方

x33g5p2x  于10个月前 转载在 其他  
字(1.1k)|赞(0)|评价(0)|浏览(100)

有序数组的平方

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

示例 1:
输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]
*
示例 2:
输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]
*
提示:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 已按 非递减顺序 排序

要求时间复杂度O(N)

解题思路

最直接的方法肯定是暴力排序了。当然不可能是时间复杂度为O(N), 那样应该为O(N^2).
既然让时间复杂度达到O(N),必然可以达到,第一个想到的是桶排序,理论上是可以的。毕竟最大也就10^4,但是写起来有点麻烦。观察一下,题目上说了已经按照非递减序列排序了。如果全部大于0相当于就不需要排序,如果存在小于0 的,必定存在一个下标flag,小于该下标的均小于0.这样我们就可以将其看成两个序列。参考归并排序,很容易就得到时间复杂度为O(N)的题解
归并排序, 点击查看哦

代码实现

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] res = new int[nums.length];
        int flag = nums.length;
        if(nums[0]<0)
        {
            for(int i = 0; i < nums.length; i++){
                if(nums[i]<0)
                    continue;
                else{
                    flag = i;
                    break;
                }
            }
            int L = flag-1;
            int R = flag;
            int i = 0;
            while(L>=0 && R<nums.length){
                res[i++] = (nums[L] + nums[R]) < 0 ? nums[R] * nums[R++] : nums[L] * nums[L--];
            }
            while(L>=0)
                res[i++] = nums[L] * nums[L--];
            while(R<nums.length)
                res[i++] =  nums[R] * nums[R++];
        }else{
            for(int i = 0; i < nums.length; i++){
                res[i] = nums[i] * nums[i];
            }
        }
        
        return res;
    }
}

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

相关文章