leetcode977：有序数组的平方（squares-of-a-sorted-array）

[carloscn]

问题描述

给你一个按 非递减顺序 排序的整数数组 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 <= 104 -104 <= nums[i] <= 104 nums 已按 非递减顺序 排序  

进阶：

请你设计时间复杂度为 O(n) 的算法解决本问题

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/squares-of-a-sorted-array

[carloscn]

问题分析

需要用O(n) 的方法进行，则在一个n的循环中解决该问题。对每个元素平方倒是很简单，主要就是负数的平方也会增大，所以平方后的数组可能是V字型，也可能是丿字型。我们可以使用双指针的方法，借助本身递增的特性，两头数据比较。

• 取左边一个元素a，再取右边一个元素b
• 判断，如果a^2 > b^2，则入b元素平方，b元素的坐标自减
• 判断，如果a^2 < b^2，则入a元素平方，a元素的坐标自加
• 判断，如果a^2 == b^2 && a坐标 不等于 b坐标，则入a的平方，再入b的平方，b元素坐标自减，a元素坐标自加。
• 当a的坐标和b的坐标相等的时候，结束循环。

pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32>
{
    let mut ret_vec:Vec<i32> = vec![];
    if nums.len() < 1 {
        return ret_vec;
    }
    let mut i:usize = 0;
    let mut j:usize = nums.len() - 1;
    while i != j {
        let a = nums[i] * nums[i];
        let b = nums[j] * nums[j];
        if a < b {
            ret_vec.insert(0,b);
            j -= 1;
        } else if a > b {
            ret_vec.insert(0, a);
            i += 1;
        }
        if a == b && i != j {
            ret_vec.insert(0, a);
            ret_vec.insert(0,b);
            j -= 1;
            i += 1;
        }
    }
    ret_vec.insert(0, nums[i] * nums[i]);
    return ret_vec;
}

[carloscn]

code

https://github.com/carloscn/structstudy/commit/39583c5dde919ecc4872465abbef942dc5e0a23f https://review.gerrithub.io/c/carloscn/structstudy/+/552055