Sort Colors II

Description

Example

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution{
public:
    /**
     * @param colors: A list of integer
     * @param k: An integer
     * @return: nothing
     */    
    void sortColors2(vector<int> &colors, int k) {
        // write your code here
        if (colors.empty() || k < 2) {
            return;
        }
        int len = colors.size();
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int minval = k + 1;
            int maxval = 0;
            // find min/max within left/right boundary
            for (int i = left; i <= right; ++i) {
                minval = min(minval, colors[i]);
                maxval = max(maxval, colors[i]);
            }
            // cout << minval << "--" << maxval << endl;
            // cout << left << "--" << right << endl;
            // cout << "---------" << endl;
            // re sort colors with min/max and left/right boundary
            // Also, left/right will be updated
            // Then element == min/max will be move to the boundary
            re_sort(colors, left, right, minval, maxval);
        }
        return;
    }
    void re_sort(vector<int>& colors, int& left, int& right, 
        int minval, int maxval
    ) {
        int start = left;
        int end = right;
        int i = start; 
        while (i <= end) {
            if (colors[i] == maxval) {
                swap(colors[i], colors[end]);
                --end;
            } else if (colors[i] == minval) {
                swap(colors[i], colors[start]);
                ++start;
                ++i;
            } else {
                ++i;
            }
        }
        left = start;
        right = end;
        return;
    }
};

Similar problems

x

Tags

x