【每日一题】LeetCode 977.有序数组的平方 (数组、双指针、排序)
题目描述
给定一个按非递减顺序排序的整数数组 nums
,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。
思路分析
方案一:暴力法
直接对数组中的每个元素进行平方操作,然后使用排序算法对结果数组进行排序。这种方法简单直观,但效率不高,因为平方操作的时间复杂度为 O(n),排序操作的时间复杂度为 O(n log n)。
方案二:双指针法
由于输入数组已经是非递减排序的,我们可以利用这一特点来优化。我们使用两个指针,一个指向数组的开始(可能包含负数),另一个指向数组的末尾。每次比较两个指针所指向的元素的平方大小,将较大的平方值放入结果数组的末尾,并移动对应的指针。这种方法的时间复杂度为 O(n),因为每个元素只被访问一次。
为什么选择双指针法
- 避免额外的排序:通过双指针法,我们避免了对整个数组进行排序,从而节省了时间。
- 从后向前填充:这样可以确保每次填充的都是当前最大的平方值,从而保持数组的非递减顺序。
- 使用绝对值比较:由于数组可能包含负数,使用绝对值比较可以确保我们总是先处理较大的数。
通过这些优化,我们能够以线性时间复杂度解决问题,大大提高了算法的效率。
输入示例
示例 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]
代码实现
方案一:暴力法
class Solution {public int[] sortedSquares(int[] nums) {for(int i = 0; i < nums.length; i++) {nums[i] = nums[i] * nums[i];}Arrays.sort(nums);return nums;}
}
方案二:双指针法
class Solution {public int[] sortedSquares(int[] nums) {// 初始化左右指针,分别指向数组的开始和结束int left = 0, right = nums.length - 1;// 由于我们需要从后向前填充结果数组,所以初始化索引为数组长度减一int i = nums.length - 1;// 创建结果数组,长度与输入数组相同int[] ans = new int[nums.length];// 当左指针小于等于右指针时,进行循环while (i >= 0) {// 比较左右指针所指向的元素的平方大小if (Math.abs(nums[left]) > Math.abs(nums[right])) {// 如果左指针所指元素的平方更大,将其平方赋值给结果数组,并移动左指针ans[i] = nums[left] * nums[left];left++;} else {// 如果右指针所指元素的平方更大或相等,将其平方赋值给结果数组,并移动右指针ans[i] = nums[right] * nums[right];right--;}// 移动结果数组的索引i--;}return ans;}
}