数据结构与算法———力扣977——双指针——python

第一个想到方法：
这个我最熟悉了

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        num = []
        for i in nums:
            num.append(i*i)
        num.sort()
        return num
1
2
3
4
5
6
7

我的进阶版本

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
    	a = [i*i for i in nums]
    	a.sort()
    	return a
1
2
3
4
5

但是人家官方的写法：真能省

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        return sorted(num * num for num in nums)
1
2
3

不过，我的目的并非如此，我是来学双指针的。
思路：定义两个指针(初始是指向开头值与末尾值)，再创建一个与原数据一样大的列表，
指针的两个数进行对比，大的就放列表（第一个放入的位置是倒数第一个，第二个放入的位置是倒数第二个，依次类推）
谁被放入，对应的指针就向自己移动的方向挪一位，直到两个指针相遇或者超过。

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
		# 这是为了防止老六 就弄一个数阴我们
        if len(nums) == 1:
            return [nums[0] * nums[0]]

        # 初始化双指针
        left = 0
        right = len(nums) - 1

        # 存储结果数组，从数组末尾开始存储
        res = [-1] * len(nums)
        # 因为是从后向前放
        site = len(nums) - 1

        # 注意这里是 <=   循环直到两个指针相遇或者超过。
        while left <= right:
            # 从两端遍历，将平方数组大得存储在 res 数组中
            if nums[left] * nums[left] < nums[right] * nums[right]:
            	# 放入位置
                res[site] = nums[right] * nums[right]
                # 指针移动
                right -= 1
            else:
                res[site] = nums[left] * nums[left]
                left += 1
			
            site -= 1

        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31