首页 > 代码库 > 荷兰国旗问题
荷兰国旗问题
时间:2014.08.07
地点:基地
----------------------------------------------------------------------------------
一、题目描述
现有红白蓝三个不同颜色的小球,乱序排列在一起,重新排列这些小球,使得红白蓝三色的同颜色的球在一起。这个问题之即荷兰国旗问题,将红白蓝三色小球想象成条状物,有序排列后正好组成荷兰国旗。如下图所示:
----------------------------------------------------------------------------------
二、思路
2.1方法一:排序
若是把颜色与数值对应起来,其实是个简单的排序问题,只不过元素取值只含3个,且有重复,不妨设为0 1 2 ,
于是采用各种排序都可解决。时间复杂度对于各种排序方法对应的时间复杂度。
2.2方法二:划分
将元素划分成三个部分,思路:
2.2.1 设置三个指针begin current end,begin current初始化指向数组首元素,end初始化指向数组尾元素
2.2.2 检查current指向的值,为 0 :则与begin交换值,然后current begin均后移一个位置
为1 :则begin不动,current后移一个位置
为2:则与end交换值,然后current后移一个位置,end前移一个位置
2.2.3重复上述过程,当current>end时停止,注意这里的条件不可以取等于(比如在序列中如果存在连续的 2 0,恰好current指向2,end指向0,则交换后为0 2,而这之前可能还有1,此时还不能终止重复过程。时间复杂符为O(n)
代码如下:
//荷兰国旗问题2014.08.07 #include<iostream> #include<vector> #include<algorithm> void Partition(std::vector<int>& vec) { auto begin = vec.begin(); auto end = vec.end() - 1; auto cursor = begin; while (cursor <= end) { if (0 == *cursor) { std::swap(*cursor, *begin); ++begin; ++cursor; } else if (1 == *cursor) ++cursor; else { std::swap(*cursor, *end); --end; } } } int main() { std::vector<int> vec{0, 1, 1,1,2,0,2,1,0, 2, 0, 2 }; Partition(vec); for (auto element : vec) std::cout << element << ' '; std::cout << std::endl; }