力扣题目链接

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

思路

暴力破解

遍历数组，每个数平方之后，排序。

归并排序

数组是非递减顺序， 只不过负数平方之后可能成为最大数了。

将左侧负数作为一个数组，右侧正数作为一个数组，归并排序。

int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    int s = -1;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] < 0) {
            s = i;
        } else {
            break;
        }
    }

    int* ans = malloc(sizeof(int) * numsSize);
    *returnSize = 0;
    int i = s, j = s + 1;
    while (i >= 0 && j < numsSize) {
        if (nums[i] * nums[i] < nums[j] * nums[j]) {
            ans[*returnSize] = nums[i] * nums[i];
            i--;
        } else {
            ans[*returnSize] = nums[j] * nums[j];
            j++;
        }
        (*returnSize)++;
    }
    if (i < 0) {
        for (;j < numsSize; j++, (*returnSize)++) {
            ans[*returnSize] = nums[j] * nums[j];
        }
    }
    if (j >= numsSize) {
        for (;i >= 0; i--, (*returnSize)++) {
            ans[*returnSize] = nums[i] * nums[i];
        }
    }

    return ans;
}

可能写复杂了，也没优化。

双指针

i指向起始位置，j指向终止位置。新数组从末端开始填入元素，谁小填谁。

int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    int k = numsSize - 1;
    *returnSize = numsSize;
    int* result = malloc(sizeof(int)**returnSize);
    for (int i = 0, j = numsSize - 1; i <= j;) {
        if (nums[i] * nums[i] < nums[j] * nums[j])  {
            result[k--] = nums[j] * nums[j];
            j--;
        }
        else {
            result[k--] = nums[i] * nums[i];
            i++;
        }
    }
    return result;
}
最后修改：2024 年 11 月 05 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏