(排序)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++;
            }
        }
    }
};
           

三、本題小知識