【LeetCode】75. Sort Colors

问题描述

https://leetcode.com/problems/sort-colors/#/description

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

算法

因为只有3个不同的元素，所以计数排序即可
首先迭代记录0,1,2一共各有多少个数，然后按照0,1,2的顺序依次填充到数组中即可。

代码

        public void sortColors(int[] nums) {
	        int[] cnt = new int[3];
	        for(int i=0;i<nums.length;i++) {
	        	cnt[nums[i]]++;
	        }
	        for(int i=0,j=0;i<nums.length;i++,cnt[j]--) {
	        	while(cnt[j]==0) {
	        		j++;
	        	}
	        	nums[i] = j;
	        }
	    }