LeetCode977有序数组的平方两种方法实现(java实现)

今天来分享的是LeetCode977有序数组的平方的实现方法，我们先来看下题目：
在这里插入图片描述
提示：我们在读题的时候一定要仔细，注意题目给定的条件是有序数组。
方法1：我们在看到题目的第一时间是无非是将数组每个元素进行平方，对平方之后的数组排个序即可，那么第一种方法的实现如下：

class Solution {
    public int[] sortedSquares(int[] nums) {

         int len=nums.length;
            int i =0;
            int j=0;
            int k=0;
            for (i=0;i<len;i++){
                nums[i]=nums[i]*nums[i];
            }
          for (j=0;j<len-1;j++){
              for (k=0;k<len-j-1;k++){
                  if(nums[k]>nums[k+1]){
                      int t=nums[k];
                      nums[k]=nums[k+1];
                      nums[k+1]=t;
                  }
              }

          }


        return nums;
    }

    }

上面的具体排序方法我用的是冒泡排序，那么利用该暴力求解法是可以通过Leetcode测试的，但是时间复杂度较高，时间复杂度为O(n*logn)；
方法二：双指针方法，我们今天主要介绍的方法为方法二
双指针的思路如下，我们注意题目是非递减数组，那么这个数组的平方最大值一定在数组的两侧，而非是中间，for example[-1,0,3,5]，这个数组平方最大值为25，因此我们根据这个特性，就可以定义两个指针left,right，一个指向数组左边，一个指向数组右边，如果发现nums[left]>nums[right]，此时开辟一个新的和原数组长度大小的数组，将nums[left]放到开辟的新数组的最后一个位置(因为题目要求我们要进行升序排序)，并将left++，如果发现如果发现nums[left]<nums[right],将nums[left]放到开辟的新数组（这里我们要进行提示下，在开辟新的数组的时候切记不可将int arr[]=nums,这样arr和nums会指向同一片地址空间）中，将right–。这样就可以完成对数组平方的排序了。那么具体代码实现如下：

class Solution {
    public int[] sortedSquares(int[] nums) {

      int i=0;
            int len=nums.length;
            int j=len-1;
            int k=len-1;
            int arr[]=new int[k+1];
            while (i<=j){
                if (nums[i]*nums[i]>nums[j]*nums[j]){
                    arr[k]=(nums[i]*nums[i]);
                    i++;
                    k--;
                }else {
                    arr[k]=(nums[j]*nums[j]);
                    j--;
                    k--;
                }
            }
            return arr;
    }

    }