977. 有序数组的平方

题目描述

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

解题思路

有个很直接的方法是，先取绝对值，然后sort，然后平方

但是这个是nlogn的算法，想要一个n的算法，那很显然需要用到数组有序这个特性。

其实平方是无关紧要的操作。

找到最小的元素，然后向两边双边移动？

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn sorted_squares(mut nums: Vec<i32>) -> Vec<i32> {
        nums.iter_mut()
            .filter(|&&mut x| x < 0)
            .for_each(|x| *x = -*x);
        let low = nums.iter().enumerate()
            .fold((0, nums[0]), |(idx, v), (jdx, &x)| {
                if x < v { (jdx, x) } else { ( idx, v ) }
            }).0;
        if low == 0 { return nums.iter().map(|x| x**x).collect() }
        let mut left = low as isize - 1;
        let mut right = low + 1;
        let n = nums.len();
        let mut v = Vec::with_capacity(n);
        v.push(nums[low]);
        // left -> 还需要处理的左侧第一个元素
        // right 还需要处理的右侧第一个元素
        while left >= 0 && right < n {
            // 判断两侧
            if nums[left as usize] < nums[right] {
                v.push(nums[left as usize]);
                left -= 1;
            } else {
                v.push(nums[right]);
                right += 1;
            }
        }
        if left < 0 {
            while right < n {
                v.push(nums[right]);
                right += 1;
            }
        } else {
            while left >= 0 {
                v.push(nums[left as usize]);
                left -= 1;
            }
        }
        v.iter().map(|x| x**x).collect()
    }
}
}

写出来了，但是很长，确实定义的每一个变量的明确含义一定要在写之前就很清楚

学习感想

数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

我是从最小数开始构建，确实麻烦，从最大的数开始构建就是一个简单一点的从两侧开始的双指针了。

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn sorted_squares(mut nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut v = Vec::with_capacity(n);
        let mut a = 0;
        let mut b = n as isize - 1;
        while a <= b {
            if nums[a as usize].abs() < nums[b as usize].abs() {
                v.push(nums[b as usize]);
                b -= 1;
            } else {
                v.push(nums[a as usize]);
                a += 1;
            }
        }
        v.iter().map(|x| x**x).rev().collect()
    }
}
}

注意是abs比较，a和b都是闭区间

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
        let mut res: Vec<i32> = vec![0i32; nums.len()];
        let mut idx: usize = 0usize;
        let mut left: usize = 0usize;
        let mut right: usize = nums.len() - 1usize;
        while idx < res.len() {
            let left_square: i32 = nums[left].pow(2u32);
            let right_square: i32 = nums[right].pow(2u32);
            use std::cmp::Ordering;
            match left_square.cmp(&right_square) {
                Ordering::Less => {
                    right -= 1usize;
                    res[nums.len() - 1usize - idx] = right_square;
                }
                _ => {
                    left += 1usize;
                    res[nums.len() - 1usize - idx] = left_square;
                }
            }
            idx += 1;
        }
        res
    }
}
}