荷兰国旗问题(把一个数组划分成<=>区域)

荷兰国旗问题一:给定一个数组和一个目标值,请把<=目标值的数放在数组的左边,大于目标值的数放在数组的右边。

图片说明
注意:<=区的起始点在-1处,它的下一个就是数组第一个元素

class HelanGuoQi1//划分成<=区和大于区
{
public:
    void helanguoqi(vector<int>& v, int target)
    {
        int se = -1;
        int tmp = 0;
        for (int i = 0; i < v.size(); i++)
        {
            if (v[i] <= target)
            {
                tmp = v[i];
                v[i] = v[se+1];
                v[se+1] = tmp;  //v[i]与<=区后一个交换
                se++;           //<=区向后扩一个
            }
        }
    }
};

荷兰国旗问题二:给定一个数组和目标值,请把<目标值的数放在数组左边,=目标值的放在数组中间,>目标值的放在数组右边。(划分成<=>区域)

图片说明
<区的初始位置为-1,>区的初始位置为size();<区推着=区往右走
终止条件:i与>区的左边界撞上了停下

class HelanGuoQi2//划分成<区,=区和大于区
{
public:
    void helanguoqi(vector<int>& v, int target)
    {
        int s = -1;
        int b = v.size();
        int i = 0;
        while(i<b)
        {
            if (v[i] < target)
            {
                mySwap(v[i], v[s+1]);
                s++;
                i++;
            }
            else if (v[i] > target)
            {
                mySwap(v[i], v[b - 1]);
                b--;
            }
            else
                i++;
        }
    }
public:
    void mySwap(int& a, int& b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
};
全部评论

相关推荐

07-09 19:25
门头沟学院 Java
这是要把每一个投校招的都开盒吗?
26届之耻将大局逆转:裁人的时候一次性追回餐费
点赞 评论 收藏
分享
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 12:05
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务