2-Color Dutch National Flag Problem

问题

a[0..n-1]中包含红元素或蓝元素;重新放置使得红元素均在蓝元素之前。

循环不变式

每一次循环，a[0...k-1]是红色

实例代码

#include <iostream>

#include <vector>

using namespace std;

class Solution {

public:

    //将仅包含1,2组成的数组用循环不变式的方式将数组转换成2在前面,1在后面。

    void loop_variant(vector<int>& vec) {

        int k = 0;

        int m = 0;

        while(m < vec.size()) {

            if (vec[m] == 2) {

                int tmp;

                tmp = vec[k];

                vec[k] = vec[m];

                vec[m] = tmp;

                k++; //每一次循环k以前的都是2

            }

            m++;

        }

    }

};

int main() {

    int arr[] = {1, 2, 1, 1, 1, 2, 2, 2, 1, 1};

    vector<int> vec(arr, arr+10);

    Solution* solution = new Solution();

    solution->loop_variant(vec);

    for (int i = 0; i < vec.size(); i++)

        cout << vec[i] << " ";

    cout << endl;

    return 0;

}

巴特西

2-Color Dutch National Flag Problem

2-Color Dutch National Flag Problem

问题

循环不变式

实例代码

最新文章

热门文章