LeetCode刷题——算法学习计划（入门部分）

题目描述

思路介绍

这题有很多种解法，我采用的是最直接最低效的数组排序法，即先将原数组的值进行平方，再排序放入另一个要返回的数组。
此外，还有进阶方法——双指针，LeetCode给出了两种双指针的方法：

• 第一种是先找到负数和非负数的分界，用两个指针分别指向这两个数字，假设指向负数的指针为p1，指向正数的指针为p2，p1每往左移，(*p1)²的平方就越大（或相等），p2每往右移，(*p2)²的平方也越大（或相等），所以它们都是非递减的，这时，对这两个非递减指针进行合并排序，即可获得一个非递减数组，具体实现见官方代码（下文）；
• 第二种双指针法是让两个指针分别从数组0位和最后一位向中间移动，选择绝对值大的倒序存入输出数组中，第二种双指针法的好处在于不用像上一种那样需要判断两个指针是否到达边界。具体实现见官方代码（下文）。

我的第一次正确提交

之前我不知道什么叫双指针，所以用了最笨的方法

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* sortedSquares(int* nums, int numsSize, int* returnSize)
{int i = 0;int j = 0;int *returnArray = (int*)malloc(sizeof(int) * numsSize);*returnSize = numsSize;for(i = 0; i < numsSize; i++){nums[i] *= nums[i];}for(i = 0; i < numsSize - 1; i++){for(j = 0; j < numsSize - i - 1; j++){if(nums[j] > nums[j + 1]){nums[j] = nums[j] ^ nums[j + 1];nums[j + 1] = nums[j] ^ nums[j + 1];nums[j] = nums[j] ^ nums[j + 1];}}}   for(i = 0; i < numsSize; i++){returnArray[i] = nums[i];}return returnArray;
}

官方版本

下面是官方版本

方法一：直接排序

思路与算法
最简单的方法就是将数组nums 中的数平方后直接排序。
——作者：LeetCode-Solution

int cmp(const void* _a, const void* _b) {int a = *(int*)_a, b = *(int*)_b;return a - b;
}int* sortedSquares(int* nums, int numsSize, int* returnSize) {(*returnSize) = numsSize;int* ans = malloc(sizeof(int) * numsSize);for (int i = 0; i < numsSize; ++i) {ans[i] = nums[i] * nums[i];}qsort(ans, numsSize, sizeof(int), cmp);return ans;
}作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array/solution/you-xu-shu-zu-de-ping-fang-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析
时间复杂度：O(nlogn)，其中 n 是数组nums 的长度。
空间复杂度：O(logn)。除了存储答案的数组以外，我们需要 O(logn) 的栈空间进行排序。
——作者：LeetCode-Solution

方法二：双指针

具体思路见官方题解

int* sortedSquares(int* nums, int numsSize, int* returnSize) {int negative = -1;for (int i = 0; i < numsSize; ++i) {if (nums[i] < 0) {negative = i;} else {break;}}int* ans = malloc(sizeof(int) * numsSize);*returnSize = 0;int i = negative, j = negative + 1;while (i >= 0 || j < numsSize) {if (i < 0) {ans[(*returnSize)++] = nums[j] * nums[j];++j;} else if (j == numsSize) {ans[(*returnSize)++] = nums[i] * nums[i];--i;} else if (nums[i] * nums[i] < nums[j] * nums[j]) {ans[(*returnSize)++] = nums[i] * nums[i];--i;} else {ans[(*returnSize)++] = nums[j] * nums[j];++j;}}return ans;
}作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array/solution/you-xu-shu-zu-de-ping-fang-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析
时间复杂度：O(n)，其中 n 是数组 nums 的长度。
空间复杂度：O(1)。除了存储答案的数组以外，我们只需要维护常量空间。
——作者：LeetCode-Solution

方法三：双指针

具体思路见官方题解

int* sortedSquares(int* nums, int numsSize, int* returnSize) {int* ans = malloc(sizeof(int) * numsSize);*returnSize = numsSize;for (int i = 0, j = numsSize - 1, pos = numsSize - 1; i <= j;) {if (nums[i] * nums[i] > nums[j] * nums[j]) {ans[pos] = nums[i] * nums[i];++i;} else {ans[pos] = nums[j] * nums[j];--j;}--pos;}return ans;
}作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array/solution/you-xu-shu-zu-de-ping-fang-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析
时间复杂度：O(n)，其中 n 是数组 nums 的长度。
空间复杂度：O(1)。除了存储答案的数组以外，我们只需要维护常量空间。
——作者：LeetCode-Solution