【每日一题】有序数组的平方

九思.

2022 年 05 月 10 日

810 次浏览

暂无评论

609字数

每日一题

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

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

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

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

发表评论时请填写正确邮箱，以便于接收通知【推荐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方法进行排序即可（快排）

双指针解法

原数组中的元素其实是有序的，主要是进行平方后数组中数据的排序
不难想到，平方后，最大的值一定是最左边或者最右边的值，不可能是中间的元素
因此，可以定义两个指针，一个指向数组首元素，一个指向数组尾元素
根据上图中的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;
    }
}