Swift 数据结构和算法( 14) 数组 +S_Leetcode977. 有序数组的平方(双指针的比较. )

概念or 注意

while 循环的最后跳出条件,

写的时候,需要计算最后一次的时候,是什么样子. 会不会漏掉index == 0的时候场景.

以及, 可能存在相等的情况下, 左右两边要如何移动.

如果, left > right , 那么左右以及相遇过了. 需要动右边 right -= 1.

如果 left < right ,左右还没有相遇, 可以动左边 left = 1.

题目

Leetcode977. 有序数组的平方leetcode.cn/problems/sq…

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

示例 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]

解题思路🙋🏻‍ ♀️

1. 暴力解题法

先计算每个数的平方，然后再对这些平方进行排序。这样的解法可以这样实现：

func sortedSquares(_ nums: [Int]) -> [Int] {
    return nums.map { $0 * $0 }.sorted()
}

• map { $0 * $0 }：对 nums 中的每个数计算平方。$0 是 map 函数的参数，代表数组中的每个元素。
• sorted()：将平方后的数组进行排序。

这个解法的时间复杂度是 O(n log n)，因为排序的时间复杂度是 O(n log n)。但是题目要求我们设计一个时间复杂度为O(n)的算法，所以这个解法并不符合题目的要求。

2. 思路 2

有如下的输入数组 nums = [-4,-1,0,3,10]，代码的主要逻辑是使用两个指针 i 和 j，分别从数组的头部和尾部进行比较和操作。

初始状态：

nums = [-4, -1, 0, 3, 10]
result = [0, 0, 0, 0, 0]
i = 0
j = 4

Step 1:

比较 nums[i] 和 nums[j] 的绝对值，即 abs(-4) 和 abs(10)，后者更大，所以将 10^2=100 放入 result 的最后一个位置，同时 j 左移一位。

nums = [-4, -1, 0, 3, 10]
result = [0, 0, 0, 0, 100]
i = 0
j = 3

Step 2:

再次比较 abs(-4) 和 abs(3)，前者更大，所以将 -4^2=16 放入 result 的倒数第二个位置，同时 i 右移一位。

nums = [-4, -1, 0, 3, 10]
result = [0, 0, 0, 16, 100]
i = 1
j = 3

Step 3:

比较 abs(-1) 和 abs(3)，后者更大，所以将 3^2=9 放入 result 的倒数第三个位置，同时 j 左移一位。

nums = [-4, -1, 0, 3, 10]
result = [0, 0, 9, 16, 100]
i = 1
j = 2

Step 4:

比较 abs(-1) 和 abs(0)，前者更大，所以将 -1^2=1 放入 result 的倒数第四个位置，同时 i 右移一位。

nums = [-4, -1, 0, 3, 10]
result = [0, 1, 9, 16, 100]
i = 2
j = 2

Step 5:

由于 i 和 j 已经相等，比较 abs(0) 和 abs(0)，将 0^2=0 放入 result 的第一个位置。此时，i 和 j 都不再移动。

nums = [-4, -1, 0, 3, 10]
result = [0, 1, 9, 16, 100]
i = 2
j = 2

最后，得到的结果 result 是 [0, 1, 9, 16, 100]，这就是原数组中每个数字的平方，按非递减顺序排序的结果。

边界思考🤔

代码

class Solution {
  func sortedSquares(_ nums: [Int]) -> [Int] {
    // 创建两个指针，一个从头部开始，一个从尾部开始
    var left  = 0
    var right = nums.count - 1
    // 创建一个新的数组，初始化所有元素为0
    var array = [Int](repeating: 0, count: nums.count)
    // 创建一个指针 p，初始位置在新数组的末尾
    var p = nums.count - 1

    // 当 p 还在新数组的范围内时，继续循环
    while p >= 0 {
      // 如果头部元素的绝对值小于尾部元素的绝对值
      if abs(nums[left]) < abs(nums[right]) {
        // 将尾部元素的平方放入新数组的 p 位置
        array[p] = nums[right] * nums[right]
        // 尾部指针向左移动一位
        right -= 1
      // 如果头部元素的绝对值大于尾部元素的绝对值
      } else if abs(nums[left]) > abs(nums[right]) {
        // 将头部元素的平方放入新数组的 p 位置
        array[p] = nums[left] * nums[left]
        // 头部指针向右移动一位
        left  = 1
      // 如果头部元素的绝对值等于尾部元素的绝对值
      } else {
        // 当 left 小于 right 时，将头部元素的平方放入新数组的 p 位置，并且头部指针向右移动一位
        if left < right {
          array[p] = nums[left] * nums[left]
          left  = 1
        // 当 left 不小于 right 时，将尾部元素的平方放入新数组的 p 位置，并且尾部指针向左移动一位
        } else {
          array[p] = nums[right] * nums[right]
          right -= 1 
        }
      }
      // 每次循环结束后，p 都向左移动一位
      p -= 1
    }

    // 返回新数组
    return array
  }
}

代码流程逻辑

开始
 |
 V
设定 left, right, array, p
 |
 V
while p >= 0:
 |   \
 |    V
 |   abs(nums[left]) < abs(nums[right])?
 |   /      \
 |  /        V
 |  是       array[p] = nums[right]^2
 |           right -= 1
 |           \
 |            V
 |           abs(nums[left]) > abs(nums[right])?
 |           /     \
 |          /       V
 |         否       array[p] = nums[left]^2
 |                  left  = 1
 |                  \
 V                   V
abs(nums[left]) == abs(nums[right]) and left < right?
|   /     \
|  /       V
| 是       array[p] = nums[left]^2
|          left  = 1
V
array[p] = nums[right]^2
right -= 1
 |
 V
p -= 1
 |
 V
结束

时空复杂度分析

O(n)

这篇好文章是转载于：学新通技术网