Description:
Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k.
Example
Given colors=[3, 2, 2, 1, 4], k=4, your code should sort colors in-place to [1, 2, 2, 3, 4].
Challenge
A rather straight forward solution is a two-pass algorithm using counting sort. That will cost O(k) extra memory. Can you do it without using extra memory?
Solution:
class Solution{
public:
/**
* @param colors: A list of integer
* @param k: An integer
* @return: nothing
*/
void sortColors2(vector<int> &colors, int k) {
auto sz = (int)colors.size();
if (sz == 0) return;
int t = 0;
for (int i = 0; i < sz; ++i) {
if (colors[i] < 0) continue;
if (colors[colors[i]-1] > 0) {
t = colors[i];
if (t > i) {
colors[i] = colors[colors[i]-1];
colors[t-1] = -1;
--i;
} else colors[t-1] = -1;
} else --colors[colors[i]-1];
}
t = sz-1;
for (int i = k-1; i >= 0; --i)
for (int j = 0; j < -colors[i]; ++j)
colors[t--] = i+1;
}
};
转载于:https://www.cnblogs.com/deofly/p/sort-colors-ii.html
