题目

点击前往

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

示例 1：

1
2
3
4
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

解题思路

暴力破解

  • 先求得平方，再利用快排进行排序。
  • 很明显暴力解法的时间复杂度是O(n + n\log n)。
1
2
3
4
5
6
7
8
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    let result = nums.map(e=> Math.pow(e,2));
    return result.sort((a,b) => a<b ? -1:1);
};

双指针

  • 双指针法：前后两个指针，将两个指针对应数平方进行比较，确定较大的一个将其置于结果数组同时将其指针向前（后）移动，直至结束。
  • 时间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    let begin = 0,end = nums.length-1;
    let result = [];
    while(begin!=end){
        if(Math.pow(nums[begin],2)>Math.pow(nums[end],2)){
            result.unshift(Math.pow(nums[begin],2));
            begin++;
        }else{
            result.unshift(Math.pow(nums[end],2));
            end--;
        }
    }
    result.unshift(Math.pow(nums[begin],2));
    return result;
};