143. Sort Colors II

묘사
n개의 대상(k종의 다른 색을 포함하고 1~k에 따라 번호를 매긴다)이 있는 그룹을 지정하여 대상을 분류하여 같은 색의 대상을 인접시키고 1,2에 따라...k의 순서로 정렬하다.
주의 사항
You are not suppose to use the library's sort function for this problem.k <= n
예제
colors=[3,2,2,1,4],k=4를 주십시오. 당신의 코드는 제자리에서 조작해서 그룹을 [1,2,2,3,4]로 만들어야 합니다.
도전하다
상당히 직접적인 해결 방안은 계수 정렬을 두 번 스캔하는 알고리즘이다.이렇게 하면 너는 O(k)의 추가 공간을 소비할 것이다.당신은 추가 공간을 사용하지 않은 상태에서 완성할 수 있습니까?

코드

4

O(nlogk)는 빠른 배열을 바탕으로 색상을 배열하지만 실제로는 빠른 배열이다. 숫자 정렬에서 무작위 데이터를 선택하는 것이 판단 기준으로 바뀌었고colorsFrom과colorsTo를 추가하여 빠른 배열의 색상 pivot`javapublic class Solution {/*

@param colors: A list of integer

@param k: An integer

@return: nothing */public void sortColors2(int[] colors, int k) { if (colors == null || colors.length == 0) { return; } rainbowsort(colors, 0, colors.length - 1, 0, k); }

public void rainbowsort(int[] colors, int left, int right, int colors From, int colors To) {//는 색상 if(colors From = = colors To) {return;if (left > right) { return; }

 int colorsMid = (colorsFrom + colorsTo) / 2;
 // left right ， ， left right l   r
 int l = left, r = right;
 //  =
 while (l <= r) {
     while (l <= r && colors[l] <= colorsMid) {
         l++;
     }
     while (l <= r && colors[r] > colorsMid) {
         r--;
     }
     if (l <= r) {
         int temp = colors[l];
         colors[l] = colors[r];
         colors[r] = temp;
         l++;
         r--;
     }
 }
 rainbowsort(colors, left, r, colorsFrom, colorsMid);
 rainbowsort(colors, l, right, colorsMid + 1, colorsTo);

} }

2. O(nlogn)  
```java
public class Solution {
    /*
     * @param colors: A list of integer
     * @param k: An integer
     * @return: nothing
     */
    public void sortColors2(int[] colors, int k) {
        if (colors == null || colors.length == 0) {
            return;
        }
        

        rainbowSort(colors, 0, colors.length - 1);
    }
    
    private void rainbowSort(int[] colors,
                             int start,
                             int end) {
        if (start > end) {
            return;
        }
        
        int left = start;
        int right = end;
        int pivot = colors[start + (end - start) / 2];
        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--;
            }
        }
        
        rainbowSort(colors, start, right);
        rainbowSort(colors, left, end);
    }
}

O(nk), not efficient

class Solution {
    /**
     * @param colors: A list of integer
     * @param k: An integer
     * @return: nothing
     */
    public void sortColors2(int[] colors, int k) {
        int count = 0;
        int left = 0;
        int right = colors.length - 1;
        while (count < k) {
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            //left right ， min max 
            for (int i = left; i <= right; i++) {
                min = Math.min(min, colors[i]);
                max = Math.max(max, colors[i]);
            }
            //  while 
            int cur = left;
            while(cur <= right) {
                if (colors[cur] == min) {
                    swap(left, cur, colors);
                    cur++;
                    left++;
                } else if (colors[cur] > min && colors[cur] < max) {
                    cur++;
                // colors[cur] == max
                } else {
                    swap(cur, right, colors);
                    right--;
                }
            }
            count += 2;
        }
    }
    
    void swap(int left, int right, int[] colors) {
        int tmp = colors[left];
        colors[left] = colors[right];
        colors[right] = tmp;
    }
}