力扣977.有序数组的平方

有序数组的平方题目地址

思路

题目要求时间复杂度要为 O ( n ) O(n) O(n),那就肯定不能用最简单的先赋值再排序的方法。
考虑原数组是一个有序的数组,即使平方后也是十分有序的一个数组。不妨假设原数组从负数到正数,就可以将其分为两部分:前面是平方递减的,后面是平方递增的(以0位分界)。
记得《算法》中说对于有序数组,归并排序是最快速的一种算法。因此这道题就可以考虑使用归并的思路进行解答。

使用两个指针分别指向原数组的首位元素和末位元素,这也是原数组平方后最大的两头(依旧不妨设其有负有正)。
从最大的两数开始比较。将较大的那一个数赋给结果数组的最后一位,再将次之的赋给前一位,以此类推(此过程无论原数组是否是有正有负都是正确的)。

代码

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        // 结果数组
        vector<int> result(nums.size());
        // 用归并的方法将这两个有序的数组归并为结果数组
        // i, j用于分别从左右两端遍历原数组,k用于赋值新数组
        int i = 0, j = nums.size() - 1, k = j;
        int left, right;    // 存储原数组的两个平方数
        while (k >= 0) {
            left = nums[i] * nums[i];
            right = nums[j] * nums[j];
            if (left > right) {
                result[k] = left;
                i++;
            }
            else {
                result[k] = right;
                j--;
            }
            k--;
        }
        return result;
    }
};

总结

每个元素都只访问一次,时间复杂度是 O ( n ) O(n) O(n)。

上一篇:LeetCode 977-有序数组的平方


下一篇:977. 有序数组的平方(Java)