手机商城源码_b2b免费发布网站大全官网_百度识图在线网页版_360推广开户

题目描述

输入：一个数组 nums，其中元素只能是 0、1 和 2。

输出：对数组进行排序，使其按顺序排列。

你需要使用 原地算法，即不能使用额外的空间来完成排序。

---

示例

示例 1

输入：

nums = [2, 0, 2, 1, 1, 0]

输出：

[0, 0, 1, 1, 2, 2]

示例 2

输入：

nums = [2, 0, 1]

输出：

[0, 1, 2]

---

解题思路

1. 计数排序

• 遍历数组，统计 0、1、2 的个数。
• 然后按照统计的数量依次将 0、1、2 填回数组。

这种方法需要两次遍历，时间复杂度为 O(n)，空间复杂度为 O(1)。

---

2. 双指针法

使用三个指针：

• p0：指向下一个应该放置 0 的位置。
• p2：指向下一个应该放置 2 的位置。
• curr：用于遍历数组。

算法过程：

1. 初始化 p0 = 0，curr = 0，p2 = n - 1。
2. 遍历数组：
   • 如果 nums[curr] == 0：将 nums[curr] 与 nums[p0] 交换，p0++，curr++。
   • 如果 nums[curr] == 2：将 nums[curr] 与 nums[p2] 交换，p2--，但此时 curr 不前进（因为交换过来的元素还需要检查）。
   • 如果 nums[curr] == 1：curr++。

这种方法只需一次遍历，时间复杂度为 O(n)，空间复杂度为 O(1)。

---

实现代码

双指针法实现

#include <stdio.h>void sortColors(int* nums, int numsSize) {int p0 = 0, curr = 0, p2 = numsSize - 1;while (curr <= p2) {if (nums[curr] == 0) {// 交换 nums[curr] 和 nums[p0]int temp = nums[curr];nums[curr] = nums[p0];nums[p0] = temp;p0++;curr++;} else if (nums[curr] == 2) {// 交换 nums[curr] 和 nums[p2]int temp = nums[curr];nums[curr] = nums[p2];nums[p2] = temp;p2--;} else {curr++;}}
}int main() {int nums[] = {2, 0, 2, 1, 1, 0};int numsSize = sizeof(nums) / sizeof(nums[0]);sortColors(nums, numsSize);// 输出排序后的数组for (int i = 0; i < numsSize; i++) {printf("%d ", nums[i]);}printf("\n");return 0;
}

---

代码解析

1. 变量初始化：

   • p0 指向当前应该放 0 的位置。
   • p2 指向当前应该放 2 的位置。
   • curr 遍历数组。

2. 循环逻辑：

   • 如果 nums[curr] == 0：
     • 交换 nums[curr] 和 nums[p0]。
     • 更新 p0 和 curr。
   • 如果 nums[curr] == 2：
     • 交换 nums[curr] 和 nums[p2]。
     • 更新 p2。
   • 如果 nums[curr] == 1：
     • 直接更新 curr。

3. 结束条件：

   • 当 curr > p2 时，所有元素已经按要求排序。

---

时间复杂度和空间复杂度

• 时间复杂度：

  • 只需一次遍历，时间复杂度为 O(n)。

• 空间复杂度：

  • 没有使用额外的空间，空间复杂度为 O(1)。