首页 > 编程语言 >LeetCode 977.有序数组的平方 (java)

LeetCode 977.有序数组的平方 (java)

时间:2024-09-11 18:50:03浏览次数:12  
标签:977 right java nums int -- 数组 LeetCode 指针

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

示例 1:

  • 输入:nums = [-4,-1,0,3,10]
  • 输出:[0,1,9,16,100]
  • 解释:平方后,数组变为 [16,1,0,9,100],排序后,数组变为 [0,1,9,16,100]

示例 2:

  • 输入:nums = [-7,-3,2,3,11]
  • 输出:[4,9,9,49,121]

本题有两种解法,暴力排序与双指针法。

暴力排序

class Solution {
    public int[] sortedSquares(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] * nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }
}

时间复杂度是 O(n + nlogn)

双指针法

双指针法(快慢指针法): 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

数组其实是有序的, 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端,不是最左边就是最右边,不可能是中间。

此时可以考虑双指针法了,i指向起始位置,j指向终止位置。

定义一个新数组result,和A数组一样的大小,让k指向result数组终止位置。

如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。

如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i]; 。

代码如下:

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] answer = new int[nums.length];
        int i = nums.length -1;
        int right = nums.length - 1;
        int left = 0;
        while(left<=right){
            if(nums[left]*nums[left] > nums[right]*nums[right]){
                answer[i--] = nums[left]*nums[left++];
            }else{
                answer[i--] = nums[right]*nums[right--];
            }
        }
        return answer;
    }
}

时间复杂度为O(n)。

标签:977,right,java,nums,int,--,数组,LeetCode,指针
From: https://blog.csdn.net/Owe_sorry/article/details/142147559

相关文章

  • LeetCode 704.二分查找 (java)
    给定一个 n 个元素有序的(升序)整型数组 nums和一个目标值 target ,写一个函数搜索 nums 中的target,如果目标值存在返回下标,否则返回-1。示例1:输入:nums=[-1,0,3,5,9,12],target=9输出:4解释:9出现在nums中并且下标为4示例 2:......
  • 关于Java中的类和对象笔记
    什么是对象:在现实世界中,随处可见的一种事物就是对象。面向对象的特点:封装性、继承性、多态性1.1封装(思想):对象的属性和行为封装起来,载体即为类。保存类数据结构的完整性,提高了程序的可维护性。1.2继承:可以继承父类的行为和属性,其中还可以添加独特的属性及行为。可复用性强......
  • Leetcode 2453. Destroy Sequential Targets | rust 实现
    题解问题描述给定一个整数数组nums和一个整数space,我们需要找到一个目标值,使得该目标值在nums中的出现次数最多。如果有多个目标值出现次数相同,则返回最小的目标值。解题思路哈希表统计:使用哈希表map来统计每个seed%space的出现次数,题干中给出的等式等价为nums[n......
  • Logstash 配置Java日志格式的方法
    Logstash是用于日志收集的开源工具,通常与Elasticsearch和Kibana一起使用,形成ELKStack(现在称为ElasticStack)。Logstash非常灵活,可以通过配置文件(通常是.conf文件)来定义数据的输入、处理和输出。对于处理Java日志,一个常见的场景是解析Java应用生成的日志文件(如使用......
  • 使用Java实现字符串中的表达式计算
    /***计算字符串表达式的值,不支持小数*<ul>*<li>加法('+')</li>*<li>减法('-')</li>*<li>乘法('*')</li>*<li>除法,保留两位小数('/')</li>*<li>取余,获取商('......
  • JavaScript 中处理接口之字段处理(1)
     遍历 res1.data(假设它是一个数组)中的所有对象并添加两个字段的方法:letres=awaitgetData({});if(Array.isArray(res.data)){for(letitemofres1.data){item.newField1='newvalue1';item.newField2='newvalue2';}WIFIList.value=res.data......
  • Java 空值判断
    //公共方法publicstaticbooleanisNull(Objecto){booleanisNull=false;if(null==o||o.toString().isEmpty()||"null".equalsIgnoreCase(o.toString())){isNull=true;}returnisNull;}......
  • PowerDesigner 逆向工程 Could not Initialize JavaVM!
    原项目的大量的表,使用PowerDesigner进行逆向工程。提示CouldnotInitializeJavaVM! 网上找到原因,PowerDesigner不可以使用64位JDK环境! 有一种不修改环境变量的方法在PowerDesigner目录下,建立一个启动批处理,如:startup.bat,在其中配置JAVA_HOME、CLASSPATH,如下例所示: ......
  • 基于java+sql企业固定资产管理系统的计算机毕设
    摘要:固定资产管理系统是一个企事业单位不可缺少的部分,它的内容对于企事业单位的决策者和管理者来说都至关重要,所以固定资产管理系统应该能够为用户提供充足的信息和快捷的查询手段。但一直以来人们使用传统人工的方式管理固定资产的信息,这种管理方式存在着许多缺点,如:效率低、保......
  • java学习之HttpClient忽略安全证书(SSLContext)
    1.我们在写https请求时候,经常会遇见安全证书(SSL)验证失败的情况,如下图。 上图异常就是因为SSL验证失败导致的,常规的做法是忽略证书认证。方法如下:第一步:需要重写认证的证书类 X509ExtendedTrustManager。第二步:创建SSLContext对象。第三步:将SSLContext对象设置到HttpClien......