力扣977 有序数组的平方

标签：977 平方 nums int 力扣 -- result 数组

有序数组的平方

题目：

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

 

暴力破解：O(nlogn)

（1）遍历，求出每个数字平方

（2）对新数组进行快排

class Solution {     public int[] sortedSquares(int[] nums) {         for(int i=0;i<nums.length;i++){             nums[i]*=nums[i];         }         quickSort(nums);         return nums;     }     public static void quickSort(int[] arr){         quickSort(arr, 0, arr.length - 1);     }
    private static void quickSort(int[] arr, int left, int right){         if (left >= right) return; //左数不小于右数，直接返回         int pivot = arr[left]; //永远以最左边的数为基准         int i = left, j = right;         while (i < j){             while (arr[j] >= pivot && i < j) --j; //从右向左遇到小于基准的数就停止             while (arr[i] <= pivot && i < j) ++i; //从左向右遇到大于基准的数就停止             if (i < j){ //交换                 int temp = arr[i];                 arr[i] = arr[j];                 arr[j] = temp;             }         }         //基准数归位（位置已确定）         arr[left] = arr[i];         arr[i] = pivot;         //分别对基准数两端的子数组进行快排         quickSort(arr, left, i - 1);         quickSort(arr, i + 1, right);     } }

双指针实现：O(n)

数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，i指向起始位置，j指向终止位置。

定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

输入数组：

-4	-1	0	3	10
i-->				<--j

结果集：

				100
				<--k

人话：i和j一个指向头，一个指向尾，比较大小，谁大谁把结果赋值给k，然后再往中间走一步，直到i和j相遇。

class Solution {     public int[] sortedSquares(int[] nums) {         int[] result=new int[nums.length];//定义一个结果集         int k=nums.length-1;         for(int i=0,j=nums.length-1;i<=j;){             if(nums[i]*nums[i]>nums[j]*nums[j]){//num[i]平方大                 result[k]=nums[i]*nums[i];                 i++;//i往中间走                 k--;             }else{//num[j]平方大                 result[k]=nums[j]*nums[j];                 j--;//j往中间走                 k--;             }         }         return result;     } }

 

标签：977,平方,nums,int,力扣,--,result,数组
From： https://www.cnblogs.com/cjhtxdy/p/16866216.html