跳转至

AC113-将数组中的所有负数移动到数组最前端，非负数移动到数组最后端

类似快速排序的思想

代码实现

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 函数 func：将数组中的所有负数移动到数组最前端，非负数移动到数组最后端
void func(int A[], int n) {
    int left = 0, right = n - 1; // 初始化两个指针，分别指向数组的起始位置和末尾位置

    // 循环条件：left 指针小于 right 指针
    while (left < right) {
        // 如果 left 指针指向的元素是负数，则向右移动 left 指针
        while (A[left] < 0 && left < right) {
            left++;
        }

        // 如果 right 指针指向的元素是非负数，则向左移动 right 指针
        while (A[right] >= 0 && left < right) {
            right--;
        }

        // 如果 left 和 right 指针未相遇，则交换它们指向的元素
        if (left < right) {
            int temp = A[left]; // 保存 A[left] 的值
            A[left] = A[right]; // 将 A[right] 的值赋给 A[left]
            A[right] = temp;    // 将保存的值赋给 A[right]
        }
    }
}

代码逻辑解析

  1. 初始化指针：
  2. left 指针从数组的起始位置（索引为 0）开始。

  3. right 指针从数组的末尾位置（索引为 n-1）开始。

  4. 循环条件：

  5. 当 left 指针小于 right 指针时，继续执行循环。

  6. 移动指针：

  7. 内层第一个 while 循环：如果 left 指针指向的元素是负数，则向右移动 left 指针。

  8. 内层第二个 while 循环：如果 right 指针指向的元素是非负数，则向左移动 right 指针。

  9. 交换元素：

  10. 如果 left 和 right 指针未相遇，说明 left 指针指向的是非负数，而 right 指针指向的是负数。

  11. 此时交换这两个元素的位置，使负数移到数组前面，非负数移到数组后面。

  12. 终止条件：

  13. 当 left 指针大于或等于 right 指针时，说明所有负数已经移动到数组的前半部分，非负数已经移动到数组的后半部分。

时间复杂度分析

  • 指针移动次数：
  • left 指针从左向右移动，最多移动 n 次。
  • right 指针从右向左移动，最多移动 n 次。

  • 每个元素最多被访问一次，因此总的指针移动次数为 O(n)。

  • 交换操作：

  • 每次交换操作的时间复杂度为 O(1)。
  • 总的交换次数不会超过 n/2。

综上，算法的时间复杂度为 O(n)。

空间复杂度分析

  • 该算法只使用了常量级别的额外空间（如变量 left, right, temp），没有使用与输入规模相关的额外空间。
  • 因此，空间复杂度为 O(1)。

较难理解部分的说明

为什么需要两个内层 while 循环？

  • 第一个内层 while 循环用于找到 left 指针指向的第一个非负数。
  • 第二个内层 while 循环用于找到 right 指针指向的第一个负数。
  • 这样可以确保每次交换操作都符合要求：将负数移到前面，非负数移到后面。

图解说明

假设数组如下：

Text Only
1
A = [3, -1, 2, -7, 5, -3]

初始状态：

Text Only
1
2
left -> A[0] = 3
right -> A[5] = -3

  • 第一次循环：left 指针指向 3（非负数），right 指针指向 -3（负数），交换两者。
    Text Only
    1
    A = [-3, -1, 2, -7, 5, 3]
  • 第二次循环：left 指针指向 -1（负数），无需交换；right 指针指向 5（非负数），无需交换。
  • 第三次循环：left 指针指向 2（非负数），right 指针指向 -7（负数），交换两者。
    Text Only
    1
    A = [-3, -1, -7, 2, 5, 3]

最终结果：

Text Only
1
A = [-3, -1, -7, 2, 5, 3]

延伸知识点

  1. 双指针法的应用：
  2. 双指针法常用于解决数组或链表的分区问题，例如快速排序中的分区操作、奇偶数分离等。

  3. 其核心思想是利用两个指针从两端向中间移动，逐步缩小搜索范围。

  4. 稳定性问题：

  5. 该算法不保证元素的相对顺序（即不稳定）。如果需要保持负数和非负数的相对顺序，可以使用其他方法（如创建辅助数组）。

  6. 扩展问题：

  7. 如果需要将数组分为三部分（如负数、零、正数），如何修改算法？
  8. 如果需要在原地完成且保持稳定性，如何设计算法？