同系列文章导读:【数据结构与算法】导读

所有文章均在本博客首发,其他平台同步更新

如果有更好的方法,欢迎指点,共同进步~~

有其他语言代码也可在留言区留言,谢谢

发表评论时请填写正确邮箱,以便于接收通知【推荐QQ邮箱】


  • 时间:2022-05-10
  • 题目序号:977
  • 难度:简单

问题描述

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

来源:力扣(LeetCode)

示例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]

提示

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 已按 非递减顺序 排序

解题思路

题解部分参考自代码随想录。如有侵权,请联系进行删除~~
  • 在解题时,我们都可以先思考暴力解法进行解题,然后再通过逐步优化,来提高代码的性能
  • 对于本题,可以通过暴力和双指针两种方法进行解决

暴力解法

  • 根据本题的题目描述,暴力解法其实很容易就能想到
  • 直接通过for循环遍历数组,让nums[i] *= nums[i]即可
  • 在遍历结束后,数组内的值就已经是平方后的值了,只不过不是按顺序排列,使用Arrays里的sort方法进行排序即可(快排)

双指针解法

img

  • 原数组中的元素其实是有序的,主要是进行平方后数组中数据的排序
  • 不难想到,平方后,最大的值一定是最左边或者最右边的值,不可能是中间的元素
  • 因此,可以定义两个指针,一个指向数组首元素,一个指向数组尾元素
  • 根据上图中的if条件进行判断循环,最终即可获得有序的平方值

代码实现

通过上述分析,分别可以通过暴力解法和双指针解法两种方式来实现移除元素

暴力解法

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

  • 时间复杂度:O(nlogn)

双指针解法

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

  • 时间复杂度:O(n)

总结

  • 一般遇到一个问题时,可以先考虑暴力解法,然后再考虑其他更加高效的算法或者对暴力解法进行不断优化,来提高算法的效率
  • 数组操作中的很多地方都会用到双指针解法,所以对于双指针一定要掌握并能够灵活的运用
  • 在有索引的地方,对于临界值的判断一定要准确,什么时候<=,什么时候<,要能够分清
最后修改:2022 年 05 月 12 日
如果觉得我的文章对你有用,请随意赞赏