首页 > 其他分享 >【LeetCode】977. 有序数组的平方

【LeetCode】977. 有序数组的平方

时间:2024-03-07 22:03:10浏览次数:33  
标签:977 平方 right nums int -- 数组 LeetCode left

题目:977. 有序数组的平方

解题思路:

  1. 分析题目,左侧负数的平方可能超过右侧正数的平方,所以考虑使用双指针法,从左右向中间遍历最大值
  2. 将遍历结果放入新创建的数组中,返回数组
  3. 由于该问题的传入数组大小不确定,故只能使用动态数组创建方法,malloc方法
  4. 导入<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;

    }
}

参考资料

  1. 有序数组的平方.双指针法
  2. Java pow() 方法

标签:977,平方,right,nums,int,--,数组,LeetCode,left
From: https://www.cnblogs.com/syr463/p/18059863

相关文章

  • 【LeetCode】209. 长度最小的子数组
    题目:209.长度最小的子数组解题思路:初始化最小长度,设置为最大值,当最小长度变小时,该值更新设置left和right指针,left指针用于记录左边界,当求和sum大于target时,左指针右移;right指针记录右边界,当求和sum小于target时,右指针右移,继续寻找符合要求的子字符串。当右边界符合题目要求......
  • 2023-03-07 leetcode写题记录
    2023-03-07leetcode写题记录目录2023-03-07leetcode写题记录148.排序链表题目链接题意解法归并排序56.合并区间题目链接题意解法复健中,第一次重新写链表题。写链表题需要注意下面这些事项:写链表时,可以把链表理解成一个数,只不过这个数有特殊含义,代表着一个地址;"->"是对地......
  • leetcode120. 三角形最小路径和
    leetcode120.三角形最小路径和这道题的关键在于想到dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j];太久没做过算法题了,连设一个dp数组都没意识到我的代码classSolution{public:intminimumTotal(vector<vector<int>>&triangle){intsize......
  • LeetCodeHot100 1.两数之和 46.字母异位词分组 128.最长连续序列
    1.两数之和https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-likedpublicint[]twoSum(int[]nums,inttarget){HashMap<Integer,Integer>map=newHashMap<>();for(inti=0;i<nums.l......
  • leetcode-快乐树
    自己写的:classSolution:defisHappy(self,n:int)->bool:n_temp=n#用n_temp保存当前的数字,以便迭代过程中使用count=0#用于计数,避免无限循环,设定最多迭代10次whilecount<10:#最多迭代10次n_str=str(n_temp......
  • 代码随想录算法训练营第二天| 977.有序数组的平方、 209.长度最小的子数组、 59.螺旋
    977.有序数组的平方https://leetcode.cn/problems/squares-of-a-sorted-array/description/publicstaticint[]sortedSquares(int[]nums){intleft=0;intright=nums.length-1;int[]result=newint[nums.length];intwrite=......
  • 代码随想录算法训练营day14 | leetcode 144. 二叉树的前序遍历、145. 二叉树的后序遍
    目录题目链接:144.二叉树的前序遍历-简单题目链接:145.二叉树的后序遍历-简单题目链接:94.二叉树的中序遍历-简单递归三要素:确定递归函数的参数和返回值:确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数,并且还要明确每次递归的返回值是什么进而确定递归......
  • leetcode-15. 三数之和 - 双指针问题
    classSolution:defthreeSum(self,nums:List[int])->List[List[int]]:nums.sort()res=[]mem=set()foriinrange(len(nums)):ifnums[i]>0:breakifi>0andnum......
  • LeetCode75 1768.交替合并字符串
    1768.交替合并字符串https://leetcode.cn/problems/merge-strings-alternately/description/?envType=study-plan-v2&envId=leetcode-75publicStringmergeAlternately(Stringword1,Stringword2){intlen1=word1.length();intlen2=word2.length()......
  • leetcode--901. 股票价格跨度(单调栈)
    记录10:002024-3-6https://leetcode.cn/problems/online-stock-span/维护一个单调递减的栈s,并且也要一个记录个数的栈count每次来一个数据,这个数据如果比s栈顶数据小,就直接放入s,并在count中记录下它的个数1如果这个数据比s栈顶数据大,就需要弹出s和count的top,来保证s是递减的......