LeetCode977——有序数组的平方-CSDN博客

LeetCode977——有序数组的平方

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

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

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

1.暴力解

首先对原来的数组进行求平方操作再选用一种排序算法对平方后的数组进行排序。

空间复杂度为O(1),时间复杂度取决于你采用的排序算法。

 public static int[] sortedSquares(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr[i]*arr[i];
        }
        //选择排序O(N2)的时间复杂度  暴力解
        insertSort(arr);
        return arr;
    }
    //选择排序
    public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int k = i;
            for (int j = i+1; j < arr.length; j++) {
                if (arr[j]<arr[k]){
                    k = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }
    }

2.双指针法

在平方后的数组首尾分别放置指针因为数组可能会存在负数且数组 非递减顺序 所以平方后的最大值必定在首尾中选取。

如果i的值大于j将i存入新数组的最后一位并执行 i++ k–如果j的值大于i将j存入新数组的最后一位并执行j-- k–这样下来 newArr便为有序的了。

时间复杂度为O(N)空间复杂度为O(N)相对于暴力解法时间复杂度更低以空间换时间。

public static int[] sortedSquares(int[] arr){
        //空间 换时间   创建一个新数组
        int[] newArr = new int[arr.length];
        //平方存入原来的数组
        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr[i]*arr[i];
        }
        //i j 分别指向平方后的数组的首尾  因为最大值 肯定在首尾
        /*i——————>0<—————————j         如果i的值大于j 将i存入新数组的最后一位 i++ k--
                                       如果j的值大于i 将j存入新数组的最后一位 j-- k--
                                       这样下来 newArr便为有序的了
        */
        int i = 0;
        int j = arr.length-1;
        int k = newArr.length-1;
        while (i<=j){
            if (arr[i]>arr[j]){
                newArr[k--] = arr[i++];
            }else {
               newArr[k--] = arr[j--];
            }
        }
        return newArr;
    }

Tips双指针的思想还是很重要的有兴趣的小伙伴可以去LeetCode27看一下巩固一下双指针的思想。

仅供学习使用