当前位置：首页 > news >正文

LeetCode:977. 有序数组的平方双指针时间复杂度O(n)

news 来源：原创 2024/9/20 16:50:02

977. 有序数组的平方

题目链接

题目描述

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

示例 1:

输入: [-4,-1,0,3,10]
输出: [0,1,9,16,100]

示例 2:

输入: [-7,-3,2,3,11]
输出: [4,9,9,49,121]

提示:

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 已按非递减顺序排序。

进阶：请你设计时间复杂度为 O(n) 的算法解决此问题。

题解

解法一：暴力法

暴力法的思路是遍历数组，将每个元素平方后放入新数组，然后排序。时间复杂度为 O(nlogn)。
这个解法我们不再赘述。

解法二：双指针法

双指针法的思路是维护两个指针，一个指向数组的左端，一个指向数组的右端。

首先，使用left和right指针分别指向数组的最左端和最右端。
然后，比较left指针指向的元素和right指针指向的元素的平方，将较大的平方放入新数组的末尾，并将left指针右移，或者将right指针左移。
这样每次选择出的，都是当前数组中，平方值最大的元素。
重复上述步骤，直到选出len(nums)个元素。

复杂度分析：

指针移动的次数为 $O (n)$ ，每个指针移动的时间复杂度为 $O (1)$ ，所以总时间复杂度为 $O (n)$ 。
空间复杂度为 $O (n)$ ，新数组的大小为 n。

代码实现

Python版本：

class Solution(object):def sortedSquares(self, nums):""":type nums: List[int]:rtype: List[int]"""right=len(nums)-1left=0res=[0]*len(nums)for i in range(right,-1,-1) :if abs(nums[right])<abs(nums[left]):res[i]=nums[left]*nums[left]left+=1else:res[i]=nums[right]*nums[right]right-=1return res

C++版本：

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int right=nums.size()-1;int left=0;vector<int> res(right+1,0);for(int i=right;i>=0;i--){if (abs(nums[left]) >= abs(nums[right])){res[i]=nums[left]*nums[left];left++;}else{res[i]=nums[right]*nums[right];right--;}}return res;}
};

Go版本：

func sortedSquares(nums []int) []int {n := len(nums)i, j, k := 0, n-1, n-1ans := make([]int, n)for i <= j {lm, rm := nums[i]*nums[i], nums[j]*nums[j]if lm > rm {ans[k] = lmi++} else {ans[k] = rmj--}k--}return ans
}