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]

挑战

一个相当直接的解决方案是使用计数排序扫描2遍的算法。这样你会花费O(k)的额外空间。你能否在不使用额外空间的情况下完成？

代码

O(nlogk), 基于快排来排颜色，实际上还是快排，从数字排序选取随机数据变成了选取颜色作为判断标准，加入 colorsFrom 和 colorsTo 来选取快排的颜色 pivot
``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, 0, k);
}

public void rainbowsort(int[] colors,
int left,
int right,
int colorsFrom,
int colorsTo) {
// 表示只有一种颜色
if (colorsFrom == colorsTo) {
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;
    }
}

最后编辑于：2019.08.18 13:49:09