Chia-ch'i

The primary purpose of this website is to motivate me to write about life, thoughts, and learning observations.

2025-06-03 lc977.Squares of a Sorted Array

date: 2025-06-03 name: aliases: tags:

  • leetcode
  • python
  • 双指针 date_last_edit: 2025-06-03 18:37 —

    2025-06-03

— creation date: 2025-06-03 18:36 — modification date: 星期二 3日 六月 2025 18:36:58

977. Squares of a Sorted Array

之前写过, 现在, 感觉可能最无脑的是全部平方一下, 然后做一遍 sort, 时间复杂度是 $O(n \text{log} n)$, 但是还是想降到 $O(n)$ 怎么办呢? 一开始的困难我觉得是在对原始的 arr 都平方之后, 之前的 sorted 这个特性就都失效了, 对于输入, nums = [-4,-1,0,3,10] 为例, 我们有这个单调性如下图所示

-4 -1 0 3 10

然后我们观察这个平方之后的图, 可以发现, 我们的单调性消失了,

16 1 0 9 100

但是只是出现了一个单调性改变的点, 那么, 我们的比较就可以从左右端点开始, 用一个 left 和一个 right 来进行比较, 那么得到的结果应该就是仍然保持单调性的(灵神:由于我们总是把更大的数放在 $ans$ 更靠右的位置), 还有, 这样我们每个点就遍历到一次, 这样时间复杂度就被降低到了 $O(n)$, 空间复杂度呢?

OK, 感觉有思路之后, 代码就简单了,python 写就更加简单了

这里我有个疑惑是, 双指针一定要用到额外的空间吗

一开始想完之后的, 写的错误的代码, 一开始想 in place 解决问题, 但是错了

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        left = 0
        right = len(nums) - 1

        while left <= right:
            # left greater than right

            left_val = nums[left]** 2
            right_val = nums[right] ** 2
            if nums[left]** 2 > nums[right]** 2:
                temp = nums[right]
                nums[right] = nums[left] ** 2
                nums[left] = temp
                right -= 1
            elif nums[left]** 2 <= nums[right]** 2:
                nums[right] = nums[right] ** 2
                right -= 1
        return nums

下面写一个正常的思路, 开一个空的 arr 来放置答案

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        left = 0
        right = len(nums) - 1
        ans = [0] * len(nums)

然后开始想如何比较的方法, 没什么好想的, 就是左边取一个右边取一个的比较

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        left = 0
        right = len(nums) - 1
        ans = [0] * (right + 1)
        n = len(nums) - 1
        while left <= right:
            left_val = nums[left] ** 2
            right_val = nums[right] ** 2

            if left_val >= right_val:
                ans[n] = left_val
                n -= 1
                left += 1
            elif left_val < right_val:
                ans[n] = right_val
                n -= 1
                right -= 1
        return ans

非常丝滑的写完了, 没有什么要额外考虑的地方, 写 while 的时候有想过就是, 这里要不要取等号, 但是好像等号和没等号结果都是一样的, 错了,这里要有等号 因为这里的变化规律是用完了当前的位置动下一个东西, 可以想象一下, 如果 left 和 right 都跳到了同一个位置上之后, 这个位置其实是没有做过任何处理的

思考

  1. 看了评论区的一些回答, 发现有人在花式的用各种排序来写这个问题, 排序,大数据量的话, 一般做到最好就是 $O(nlogn)$, 感觉没毛病, 是不是就是说一定要有空间这个 trade off, 才可以做到 $O(n)$
  2. 参考上面一开始出错的部分, 是不是就是说不能 in place 的做

2025

2025-06-03 lc704. Binary Search

4 minute read

date: 2025-06-03 name: aliases: tags: leetcode python BinarySearch date_last_edit: 2025-06-03 16:46 — 2025-06-03

Back to top ↑

2024

Back to top ↑

2023

Back to top ↑