给定一个包含红色、白色和蓝色、共 n
个元素的数组 nums
,原地 对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
我们使用整数 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
进阶:
- 你能想出一个仅使用常数空间的一趟扫描算法吗?
写就写进阶的解,这还不简单,直接上代码,看不懂可以私信或评论,第一时间解答
class Solution {
/**这个题目也是听起来比较唬人,但是这个仔细想想如果按照数字来看,不就是红色最小,白色居中,蓝色最大吗
这是啥问题?荷兰国旗啊,下面我们用荷兰国旗问题解一下,这就是荷兰国旗里的Partition */
public void sortColors(int[] nums) {
/**如果就一个那就直接返回吧,没啥可操作的*/
if(nums.length == 1) {
return;
}
/**开始进行划分,redLast表示确定的红的最后一个位置,目前还没有,blueFirst表示确定的蓝色的第一个位置,目前也还没有*/
int redLast = -1;
int blueFirst = nums.length;
int cur = 0;
while(cur < blueFirst) {
/**等于的不管 */
if(nums[cur] == 1) {
cur ++;
/**如果是0和红色的最后一个位置的下一个交换,扩充红色区,因为换的是之前的位置,所以这里cur不用验证,也直接++ */
} else if(nums[cur] == 0) {
swap(nums, cur++, ++redLast);
} else {
/**如果是2,就和蓝色的最后一个位置的前一个交换,扩充红色区,但是这个是从后面缓过来的,需要看看*/
swap(nums, cur, --blueFirst);
}
}
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
标签:cur,nums,int,Leecode,++,75,红色,100,blueFirst
From: https://blog.csdn.net/Chang_Yafei/article/details/142695311