143 · Sort Colors II [LintCode]

一刷 05/2022

Time O(nlogk)

Space O(1)

public class Solution {

/**

* @param colors: A list of integer

* @param k: An integer

* @return: nothing

*/

public void sortColors2(int[] colors, int k) {

// Every time devide the color by 2 and partition the colors

// Then we got O(nlogk) time complexity

if (colors == null) {

return;

}

sortColorsHelper(colors, 0, colors.length - 1, 1, k);

}

private void sortColorsHelper(int[] colors, int start, int end, int kStart, int kEnd) {

if (kStart == kEnd) {

return;

}

// k/2 k - k/2

// 1111 22222

// when k = 2, we want sort [start right] [left end]

// when k = 3, we wnat sort

int pivot = (kStart + kEnd) / 2; // the pivot color

int left = start, right = end;

while (left <= right) {

while (left <= right && colors[left] <= pivot) {

left++;

}

while (left <= right && colors[right] > pivot) {

right--;

}

if (left <= right) {

int temp = colors[left];

colors[left] = colors[right];

colors[right] = temp;

left++;

right--;

}

}

// left is the first index that has color > pivot

sortColorsHelper(colors, start, left - 1, kStart, pivot);

sortColorsHelper(colors, left, end, pivot + 1, kEnd);

}

}