算法

算法(4)-有序数组的平方与左右指针

题目(easy)：

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

思路

暴力破解就是遍历一遍之后再排序，时间复杂度为 O(n+nlogn)。

双指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const sortedSquares = (nums) => {
    let n = nums.length;
    let res = new Array(n).fill(0);
    let i = 0;
    let j = n - 1;
    let k = n - 1;
    while(i <= j) {
        let left = nums[i] * nums[i];
        let right = nums[j] * nums[j];
        if (left < right) {
            res[k--] = right;
            j--;
        } else {
            res[k--] = left;
            i++;
        }
    }
    return res;
}

时间复杂度为 O(n)。