75颜色分类-hot100-java-爱代码爱编程
问题描述来源leetcode
一、问题描述:
75颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 0 1 2
必须在不使用库内置的 sort 函数的情况下解决这个问题。 红 白 蓝
示例 1: 输入:nums = [2,0,2,1,1,0] 输出:[0,0,1,1,2,2]
示例 2: 输入:nums = [2,0,1] 输出:[0,1,2]
提示: n == nums.length 1 <= n <= 300 nums[i] 为 0、1 或 2
进阶: 你能想出一个仅使用常数空间的一趟扫描算法吗?
二、题解
和这道有类似的思路:21合并两个有序链表-hot100-Java
做过这个类似的后应该可以很快做出来了·。
思路
这里考的应该是数学吧。
本来想用哈希来处理的,但是还是一开始就用了最优解吧,。一开始的解可能不是最优,但是用其他功能丰富的数据结构会方便很多,做出来的概率也大,如果一开始直奔最优解,那么有可能做不出来或者很久才做出来。但是这个题好像很简单,就直接往最优解的思路写了。
首先,不能用内部排序,也不能用较多的空间。本来也没想到要用较多的空间,直接想到了最优解:
先遍历一次找出3种颜色的个数,然后确定好区间,3种颜色的个数可以划分出3段不同索引范围的空间,于是就将每段索引对应的元素改成对应的数字即可。这里难点就是划分区间,要找到索引边界。思考一下就知道了。
题解:
class Solution {
public void sortColors(int[] nums) {
int red = 0;
int white = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
red++;
} else if (nums[i] == 1) {
white++;
}
}
int index = 0;//如果red = 2 [0,1,2],if red = 0,skip
for (; index < red; index++) nums[index] = 0;
for (; index < red + white; index++) nums[index] = 1;
for (; index < nums.length; index++) nums[index] = 2;
}
}