题目:977. 有序数组的平方
解题思路:
- 分析题目,左侧负数的平方可能超过右侧正数的平方,所以考虑使用双指针法,从左右向中间遍历最大值
- 将遍历结果放入新创建的数组中,返回数组
- 由于该问题的传入数组大小不确定,故只能使用动态数组创建方法,malloc方法
- 导入<math.h>,使用abs绝对值比较函数,以及pow求幂函数
C代码实现
#include<math.h>
int* sortedSquares(int* nums, int numsSize, int* returnSize){
// 返回数组大小为原数组大小
*returnSize = numsSize;
// 创建两个指针,left指向数组开头,right指向数组结尾
int left=0, right=numsSize-1;
int k=numsSize-1;
// 创建返回的数组result
int* result = (int*)malloc(sizeof(int) * numsSize);
while(k>=0){
if(abs(nums[left])>abs(nums[right])){
result[k--] = pow(nums[left++], 2);
} else {
result[k--] = pow(nums[right--], 2);
}
}
return result;
}
解题思路
- 给定一个非递减序列的数组,要求返回每个数字的平方,且按照非递减序列排序;观察数组可知,一个数进行平方之后,最大值只能出现在数组头或数组尾,因而比较两位置的平方后填入res数组中即可
- 设置双指针,left指向头,right指向尾;将结果按照从大到小的顺序倒序放在res中即可
- 如果将left所指值的平方,放在res中,那么将left右移;否则,将right左移
- 需要注意的是,如果使用Math.pow函数,其返回值是double类型,需要将其类型转化为int类型
Java代码实现
// 解法一
class Solution {
public int[] sortedSquares(int[] nums) {
int len = nums.length;
int[] res = new int[len];
int left = 0;
int right = len-1;
for(int i=len-1; i>=0; i--) {
// if(nums[left] * nums[left] > nums[right] * nums[right]) {
// res[i] = nums[left] * nums[left];
// left++;
// } else {
// res[i] = nums[right] * nums[right];
// right--;
// }
res[i] = Math.abs(nums[left]) > Math.abs(nums[right]) ? (int) Math.pow(Math.abs(nums[left++]), 2) : (int) Math.pow(Math.abs(nums[right--]), 2);
}
return res;
}
}
// 解法二
class Solution {
public int[] sortedSquares(int[] nums) {
int left=0, right = nums.length-1;
int len = nums.length;
int[] result = new int[len];
while(left<=right){
if(nums[left]*nums[left] > nums[right]*nums[right]) {
result[--len] = nums[left]*nums[left];
left++;
} else {
result[--len] = nums[right]*nums[right];
right--;
}
}
return result;
}
}