Sort Colors Ii

Sort Colors Ii

题目地址

题目描述

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.

代码

public class Solution {
public void sortColors2(int[] colors, int k) {
if (colors == null || colors.length == 0) return;
rainbowSort(colors, 0, colors.length - 1, 1, k);
}
public void rainbowSort(int[] colrs,
int left,
int right,
int colorFrom,
int colorTo) {
if (colorFrom == colorTo) return;
if (left >= right) return;
int colorMid = (colorFrom + colorTo) / 2;
int l = left, r = right;
while (l <= r) {
while (l <= r && colors[l] <= colorMid) {
l++;
}
while (l <= r && colors[r] > colorMid) {
r--;
}
if (l <= r) {
int temp = colors[l];
colors[l] = colors[r];
colors[r] = temp;
l++;
r--;
}
}
rainbowSort(colors, left, r, colorFrom, colorMid);
rainbowSort(colors, l, right, colorMid + 1, colorTo);
}
}