977. 有序数组的平方
给你一个按非递减顺序排序的整数数组 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、定义left指向起始位置,right指向终止位置。
2、定义一个新数组result,和A数组一样的大小,让index指向result数组最后一个元素位置。
如果A[left] * A[left] < A[right] * A[right] 那么result[index–] = A[right] * A[right]; 。
如果A[left] * A[left] >= A[right] * A[right] 那么result[index–] = A[left] * A[left]; 。
如动画所示:
package com.codernav.demo.leetcode.array.removeelement; import java.util.Arrays; /** * 977. 有序数组的平方 * 给你一个按非递减顺序排序的整数数组 nums,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。 * 原文地址:https://www.codernav.com/2907.html * 更多算法详解:https://www.codernav.com */ public class Q_977_1 { public static void main(String[] args) { int[] result = f(new int[]{-4, -1, 0, 3, 10}); // 0,1,9,16,100 System.out.println(Arrays.toString(result)); } private static int[] f(int[] nums) { int right = nums.length - 1; int left = 0; int[] result = new int[nums.length]; int index = result.length - 1; while (left <= right) { if (nums[left] * nums[left] > nums[right] * nums[right]) { result[index--] = nums[left] * nums[left]; ++left; } else { result[index--] = nums[right] * nums[right]; --right; } } return result; } }
以下写法也是可以的:
package com.codernav.demo.leetcode.array.removeelement; import java.util.Arrays; /** * 977. 有序数组的平方 * 给你一个按非递减顺序排序的整数数组 nums,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。 * 原文地址:https://www.codernav.com/2907.html * 更多算法详解:https://www.codernav.com */ public class Q_977_1 { public static void main(String[] args) { int[] result = f(new int[]{-4, -1, 0, 3, 10}); // 0,1,9,16,100 System.out.println(Arrays.toString(result)); } private static int[] f(int[] nums) { // 定义左指针 int left = 0; // 定义右指针 int right = nums.length - 1; // 定义一个新数组,用来存放元素平方值 int[] result = new int[nums.length]; // 定义一个下标,指向新数组最后一个元素位置 int index = result.length - 1; while (left <= right) { // 最左边元素平方比最右边元素平方大,取最左边元素平方值 if (nums[left] * nums[left] > nums[right] * nums[right]) { result[index] = nums[left] * nums[left]; index--; // 取了left,下次就不取这个值了,所以left++ left++; } else { // 最右边元素平方比最左边元素平方大,取最右边元素平方值 result[index] = nums[right] * nums[right]; index--; // 取了right,下次就不取这个值了,所以right++ right--; } } return result; } }
© 版权声明
文章版权归作者所有,未经允许请勿转载。
相关文章
暂无评论...