标签搜索

有序数组的平方 双指针法

Lan
Lan
2022-11-16 / 0 评论 / 6 阅读 / 正在检测是否收录...

给你一个按 非递减顺序 排序的整数数组 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 <vector>
#include <stdio.h>

using namespace std;

int main() {
    // 初始数组
    vector<int> nums = {-4,-1,0,3,10};
    // 存放结果的数组
    vector<int> 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;
}

www.lanol.cn

0

评论 (0)

取消