有序数组的平方
思路
- 如果我们不考虑进阶条件，即时间复杂度为O(n)，那这题就很简单了，我们可以先将数组所有的数先平方，再利用选择排序对新组进行排序处理就好了，但这样的时间复杂度为O(n2)
- 那怎么将时间复杂度减小到O(n)呢？
- 我们知道，因为有负数的存在，使得可能存在负数的平方大于正数的平方这种情况。
- 但由于原数组是一个非递减数组，新数组的最大值一定是原数组第一个数（最小值）的平方或最后一个数（最大值）的平方
- 因此这题我们就可以采用双指针中对撞指针的思想来解决这题
- 我们首先建立一个和原数组同等大小的新数组，用来存放平方数
- 设新数组下标为index，并从最大值开始存入数据
- 定义左指针left指向原数组的第一个元素，右指针right指向原数组的最后一个元素
- 比较left指向元素的绝对值和right指向元素的绝对值，将较大元素的平方存入新数组中，同时对left，right，index做相应处理，直到遍历完原数组。
- 如下图就实现对nums[-4,-1,0,3,10]实现对元素绝对值从小到大的排序
- 这样时间复杂度就变为了O(n)
实现代码
暴力解法
/** * Note: The returned array must be malloced, assume caller calls free(). */ void selectSort(int *nums,int numsSize) //选择排序，时间复杂度为O(n^2) { for(int i=0;i<numsSize-1;i++) for(int j=i+1;j<numsSize;j++) if(nums[j] < nums[i]) { int temp = nums[j]; nums[j] = nums[i]; nums[i] = temp; } } int* sortedSquares(int* nums, int numsSize, int* returnSize){ *returnSize = numsSize; for(int i=0;i<numsSize;i++) nums[i] = nums[i] * nums[i]; selectSort(nums,numsSize); //对平方数进行排序 return nums; }
双指针——对撞指针
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* sortedSquares(int* nums, int numsSize, int* returnSize){ *returnSize = numsSize; int *newnums = (int *)malloc(sizeof(int) * numsSize); //申请新数组内存 int left = 0, right = numsSize - 1; int index = numsSize - 1; while(left <= right) { if(fabs(nums[left]) > fabs(nums[right])) //比较绝对值大小 { newnums[index--] = nums[left] * nums[left]; left++; } else { newnums[index--] = nums[right] * nums[right]; right--; } } return newnums; //返回新数组 }
