【LeetCode数组#3有序数组的平方】有序数组平方

有序数组的平方

力扣题目链接(opens new window)

给你一个按非递减顺序 排序的整数数组 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]

初见思路

由题意，我们需要做两件事情：

1、将所给数组内的元素取平方

2、给平方之后的元素按升序重新排序

两种思路

一种是所有元素取平方后用sort函数排序；

另一种思路，若源数组存在负数，那么其平方后的值肯定会变大，因此顺序也会变化

那么先把数组中的所有值取绝对值，然后排序，最后再将每个数取平方

用什么方法排序？冒泡？以下是暴力方法解

class Solution {
    public int[] sortedSquares(int[] nums) {
        int tmp = 0;
        for(int i = 0; i < nums.length - 1; i++){
            for(int j = 0; j < nums.length - 1 - i; j++){
                //先把负的元素取反，然后冒泡排序
                if(nums[i] < 0){
                    nums[i] = -nums[i];
                }
                if(nums[j] > nums[j + 1]){
                    tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                } 
            }
        }
        //最后把数组内元素取平方
        for(int k = 0; k < nums.length; k++){
            nums[k] = nums[k]*nums[k];
        }
    return nums;
    }
}

可优化的点太多了，排序方法、取平方方法都可以改进

常规思路

这里仍可以用双指针的思想去做

首先这里有一个规律：在有序数组中，能够在平方之后出现的最大值的元素一定在数组的两端，不可能在数组中间

基于上述现象就可以使用双指针来解决问题

两个指针分别位于数组的两端，在遍历过程中不断向数组中心移动

此外，我们还需要额外定义一个指针用于表示新数组的下标

注意，题目没有要求原地操作，因此可以新建一个数组用于存放元素

因为我们需要从大到小排序，所以新数组指针的初值就设置为数组长度-1即可

解题模板

按照上面的思路写就行

Java版

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] newnums = new int[nums.length];
        int k = newnums.length -1;
        for(int i = 0, j = nums.length - 1; i <= j; ){//不要忘了=，要不然就会漏一个
            if(nums[i] * nums[i] > nums[j] * nums[j]){
                newnums[k--] = nums[i] * nums[i];//注意是后--
                //k -= 1;//要么就 这样写
                ++i;
            }else{//小于、等于的情况
                newnums[k--] = nums[j] * nums[j];
                --j;
            }
        }
        return newnums;
    }
}

Python版

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        i,j,k = 0,n - 1,n - 1
        ans = [-1] * n
        while i <= j:
            lm = nums[i] ** 2
            rm = nums[j] ** 2
            if lm > rm:
                ans[k] = lm
                i += 1
            else:
                ans[k] = rm
                j -= 1
            k -= 1
        return ans