Leetcode_75_Sort Colors

本文是在学习中的总结，欢迎转载但请注明出处：http://blog.csdn.net/pistolove/article/details/43302343

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.

思路：

（1）题意为给定一个数组，里面含有红白蓝三种颜色（顺序是打乱的），将其调整为红-->白-->蓝的顺序。其中，0，1，2分别对应红，白，蓝。

（2）该题的实质就是一个排序操作。只不过相同的元素比较多，需要确定下来。本文使用的方法比较简单，首先，遍历数组，确定0，1，2的个数；然后，再对数组进行遍历，依次将0，1，2填入数组中。具体操作为，只要0的个数大于零，就将0填入数组，然后个数减1，直到0全部放入数组为止，继续将1和2按照其对应的个数放入数组中。最后，所得的数组中就是以连续的0-->1-->2的顺序分布。

（3）希望本文对你有所帮助。

算法代码实现如下：

	/**
	 *
	 * @author liqq
	 */
	public void sortColors(int[] A) {
		if (A == null || A.length <= 1)
			return;

		int _zeor = 0;
		int _one = 0;
		int _two = 0;

		for (int i = 0; i < A.length; i++) {
			if (A[i] == 0)
				_zeor++;
			if (A[i] == 1)
				_one++;
			if (A[i] == 2)
				_two++;
		}

		for (int i = 0; i < A.length; i++) {
			if (_zeor > 0) {
				A[i] = 0;
				_zeor--;
				continue;
			}
			if (_one > 0) {
				A[i] = 1;
				_one--;
				continue;
			}

			if (_two > 0) {
				A[i] = 2;
				_two--;
			}
		}
	}

巴特西

Leetcode_75_Sort Colors

最新文章

热门文章