有序数组的平方双指针法

SingYi

发布于 2023-08-23 08:11:13

18800

代码可运行

文章被收录于专栏：Lan小站Lan小站

运行总次数：0

代码可运行

给你一个按非递减顺序排序的整数数组 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] 双指针法数组其实是有序的，只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。此时可以考虑双指针法了，i指向起始位置，j指向终止位置。定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。如果A[i] A[i] < A[j] A[j] 那么result[k--] = A[j] * A[j]; 。如果A[i] A[i] >= A[j] A[j] 那么result[k--] = A[i] * A[i]; 。 https://www.yuque.com/lxyo/course/vb7zmoutvnp5zeeo?#XjKZc

//
// Created by Lan on 2022/11/16.
//
#include 
#include 

using namespace std;

int main() {
    // 初始数组
    vector nums = {-4,-1,0,3,10};
    // 存放结果的数组
    vector result(nums.size(), 0);
    // 用于存结果的指针
    int k = nums.size() - 1;
    // 因为原数组是有序的，但是由于平方之后有的负数会比正数大，所以可以从两边
    // 同时往中间走，直到左右指针相遇。
    // 遍历一次，首指针的平方与尾指针的平方比较
    // 选择大的，然后放在结果指针，然后结果指针-1
    for (int i = 0, j = nums.size() - 1; i <= j;) {
        if (nums[i] * nums[i] > nums[j] * nums[j]) {
            result[k--] = nums[i] * nums[i];
            i++;
        } else {
            result[k--] = nums[j] * nums[j];
            j--;
        }
    }
    // 遍历输出结果
    for (int i = 0; i < result.size(); ++i) {
        printf("%d\t", result[i]);
    }
    return 1;
}