c++2、设有顺序放置的 n 个桶,每个桶中装有一粒砾石,每粒砾石颜色是红、白、蓝之一。求重新调整这些砾石的位置,使得所有红色砾石在前,所有白色砾石居中,所有蓝色砾石在后,重新安排时对每粒砾石的颜色只能看一次,并用只允许交换操作为调整砾石的位置。
时间: 2024-03-18 10:44:56 浏览: 64
这是一道荷兰国旗问题,可以使用三指针法来解决。
具体来说,我们可以使用三个指针 `p0`、`p1` 和 `p2` 分别指向当前已经排好序的红色区域的下一个位置、当前已经排好序的白色区域的下一个位置,以及当前已经排好序的蓝色区域的前一个位置。初始时,`p0` 和 `p2` 分别指向第一个桶和最后一个桶,`p1` 指向第一个桶。我们从左往右遍历所有桶,对于每个桶,分别处理以下三种情况:
1. 如果当前桶中的砾石是红色,那么我们将其交换到红色区域的末尾,即将 `p1` 和 `p0` 指向的桶中的砾石交换,然后将 `p0` 和 `p1` 向后移动一位;
2. 如果当前桶中的砾石是白色,那么它已经在白色区域中,不需要进行任何操作,直接将 `p1` 向后移动一位;
3. 如果当前桶中的砾石是蓝色,那么我们将其交换到蓝色区域的开头,即将 `p1` 和 `p2` 指向的桶中的砾石交换,然后将 `p2` 向前移动一位。
重复上述过程,直到遍历完所有的桶,此时所有砾石的颜色就已经按照要求排好序了。
下面是对应的 C++ 代码实现:
```c++
void sortColors(vector<int>& nums) {
int n = nums.size();
int p0 = 0, p1 = 0, p2 = n - 1;
while (p1 <= p2) {
if (nums[p1] == 0) { // 红色
swap(nums[p0], nums[p1]);
p0++;
p1++;
} else if (nums[p1] == 1) { // 白色
p1++;
} else { // 蓝色
swap(nums[p1], nums[p2]);
p2--;
}
}
}
```
在这个算法中,我们使用了三个指针 `p0`、`p1` 和 `p2`,它们分别指向红色区域的下一个位置、白色区域的下一个位置,以及蓝色区域的前一个位置。我们从左往右遍历所有桶,对于每个桶,分别处理三种情况:如果是红色,交换到红色区域的末尾;如果是白色,跳过不处理;如果是蓝色,交换到蓝色区域的开头。最终,我们得到的就是按照要求排好序的砾石序列。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)