做ui要上那些网站,青岛如何做网站seo,苏州公司网站开发,网站制作苏州企业给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums #xff0c;原地 对它们进行排序#xff0c;使得相同颜色的元素相邻#xff0c;并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解…给定一个包含红色、白色和蓝色、共 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.length1 n 300nums[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;}
}
