(排序)leetcode75. 颜色分类

文章目录

• 一、题目
• • 1、题目描述
  • 2、基础框架
  • 3、原题链接
• 二、解题报告
• • 1、思路分析
  • 2、时间复杂度
  • 3、代码详解
• 三、本题小知识

一、题目

1、题目描述

2、基础框架

• C++版本给出的基础框架如下：

3、原题链接

https://leetcode.cn/problems/sort-colors/

二、解题报告

1、思路分析

   ( 1 ) (1) (1)采用双指针p0和p1，初始值为0

   ( 2 ) (2) (2)遍历数组，当遇到1时，将当前值与下标p1互换。

   ( 3 ) (3) (3)当遇到0时，将当前值与下标p0互换，如果p0下标再p1下标之前，则互换后继续将换后当前位置的值与p1下标互换。因为与p0互换时，如果p0在p1之前，那么会把1换出去。然后p0和p1同时进1。

   ( 4 ) (4) (4)p0永远小于或等于p1。

2、时间复杂度

3、代码详解

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int p1 = 0;
        int p0 = 0;
        int n = nums.size();
        for (int i=0; i < n; i++) {
            if (nums[i] == 1) {
                swap(nums[p1], nums[i]);
                p1++;
            } else if (nums[i] == 0) {
                swap(nums[p0], nums[i]);
                if (p0 < p1) {
                    swap(nums[p1], nums[i]);
                }
                p0++;
                p1++;
            }
        }
    }
};
           

三、本题小知识