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

数组

 2024/03/06 

题目(easy)：

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

思路

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

双指针法

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)。

原文作者：Yizhou Shen

原文链接：http://shenyizhou.github.io/2024/03/06/2024-03-06-%E7%AE%97%E6%B3%95(4)-%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9%E4%B8%8E%E5%B7%A6%E5%8F%B3%E6%8C%87%E9%92%88/

发表日期：March 6th 2024, 8:32:57 pm

更新日期：March 11th 2024, 12:07:41 pm

Next Post

算法(5)-长度最小的子数组和滑动窗口
Previous Post

算法(3)-移除元素与快慢指针

CATALOG

1. 题目(easy)：
2. 思路
1. 2.1. 双指针法