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

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)-1
        left=0
        res=[0]*len(nums)
        for i in range(right,-1,-1) :
            if abs(nums[right])<abs(nums[left]):
                res[i]=nums[left]*nums[left]
                left+=1
            else:
                res[i]=nums[right]*nums[right]
                right-=1
        return 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-1
	ans := make([]int, n)
	for i <= j {
		lm, rm := nums[i]*nums[i], nums[j]*nums[j]
		if lm > rm {
			ans[k] = lm
			i++
		} else {
			ans[k] = rm
			j--
		}
		k--
	}
	return ans
}