package LeetCode;

//https://leetcode.com/problems/sort-colors/description/
public class Leetcode75 {

    /**
     * 扫描出现的频率，然后根据频率再填充回去
     *
     * @param nums
     */
    // 时间复杂度: O(n)
    // 空间复杂度: O(1)
    public void sortColors(int[] nums) {
        int[] count = {0, 0, 0};    // 存放0, 1, 2三个元素的频率
        for (int i = 0; i < nums.length; i++) {
            assert nums[i] >= 0 && nums[i] <= 2;
            count[nums[i]]++;
        }
        int index = 0;
        for (int i = 0; i < count[0]; i++)
            nums[index++] = 0;
        for (int i = 0; i < count[1]; i++)
            nums[index++] = 1;
        for (int i = 0; i < count[2]; i++)
            nums[index++] = 2;
    }


    /**
     * 三路快排思路
     *
     * @param nums
     */
    // 时间复杂度: O(n)
    // 空间复杂度: O(1)
    public void sortColors2(int[] nums) {

        int zero = -1;          // [0...zero] == 0
        int two = nums.length;  // [two...n-1] == 2
        for (int i = 0; i < two; ) {
            if (nums[i] == 1)
                i++;
            else if (nums[i] == 2)
                swap(nums, i, --two);
            else { // nums[i] == 0
                assert nums[i] == 0;
                swap(nums, ++zero, i++);
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}