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

本文主要是介绍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;}}