荷兰国旗问题

荷兰国旗问题也叫颜色分类问题.

题目描述

给定一个包含红色, 白色和蓝色, 共 n 个元素的数组 nums , 原地对它们进行排序,

使得相同颜色的元素相邻, 并按照红色, 白色, 蓝色顺序排列.

我们使用整数 0, 1 和 2 分别表示红色, 白色和蓝色.

必须在不使用库的 sort 函数的情况下解决这个问题.

示例 1:

输入:nums = [2, 0, 2, 1, 1, 0]
输出:[0, 0, 1, 1, 2, 2]
示例 2:

输入:nums = [2, 0, 1]
输出:[0, 1, 2]

投机取巧

我知道要用指针来做, 但是具体怎么做我不会, 突然就想到了一个投机取巧的方法:

class Solution {
public:
    void sortColors(vector<int>& nums) {

        // [2 1 2 0 1 0]

        if (nums.size() == 0 || nums.size() == 1) return;

        // 既然你状态有限, 那我直接对状态进行计数不就可以了, 哈哈
        int counter[] = { 0, 0, 0 };

        for (auto i : nums) {
            if (i == 0)
                counter[0]++;
            else if (i == 1)
                counter[1]++;
            else
                counter[2]++;
        }

        int begin = 0;
        int end = 0;
        for (int i = 0; i < 3; i++) {
            end = begin + counter[i];

            for (int j = begin; j < end; j++)
                nums[j] = i;
            begin = end;
        }
    }
};

学一下正儿八经的做法吧, 应该是快排里面的一个基操了.

单指针

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

先把所有的 0 放到最左边, 再把所有的 1 放到所有 0 的后边, 就可以得到结果了.

双指针

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int p0 = 0, p1 = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) {
                swap(nums[i], nums[p1]);
                ++p1;
            } else if (nums[i] == 0) {
                swap(nums[i], nums[p0]);
                // 这步有点奇怪为什么要换
                if (p0 < p1) {
                    swap(nums[i], nums[p1]);
                }
                ++p0;
                ++p1;
            }
        }
    }
};

下面是其他例子的分析

双指针 (二)

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

快排中的子过程

下面这个是我写的:

class Solution {
public:
    void partition(vector<int>& nums) {
        int n = nums.size();
        int p0 = 0, p1 = n - 1;
        int s = 0;
        while (p0 < p1) {
            while (nums[p1] > nums[s])
                --p1;

            if (p1 != s) {
                swap(nums[s], nums[p1]);
                s = p1;
                --p1;
            }

            while (nums[p0] < nums[s]) {
                ++p0;
            }

            if (p0 != s) {
                swap(nums[s], nums[p0]);
                s = p0;
                ++p0;
            }

            print(nums);
        }
    }
};

网上写的:

#include<iostream>
using namespace std;
void quickSort(int a[],int,int);
int main()
{
    int array[]={34,65,12,43,67,5,78,10,3,70},k;
    int len=sizeof(array)/sizeof(int);
    cout<<"The orginal arrayare:"<<endl;
    for(k=0;k<len;k++)
        cout<<array[k]<<",";
    cout<<endl;
    quickSort(array,0,len-1);
    cout<<"The sorted arrayare:"<<endl;
    for(k=0;k<len;k++)
        cout<<array[k]<<",";
    cout<<endl;
    system("pause");
    return 0;
}

void quickSort(int s[], int l, int r)
{
    if (l< r)
    {
        int i = l, j = r, x = s[l];
        while (i < j)
        {
            while(i < j && s[j]>= x) // 从右向左找第一个小于x的数
                j--;
            if(i < j)
                s[i++] = s[j];
            while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数
                i++;
            if(i < j)
                s[j--] = s[i];
        }
        s[i] = x;
        quickSort(s, l, i - 1); // 递归调用
        quickSort(s, i + 1, r);
    }
}