色彩分类
题目形容:给定一个蕴含红色、红色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得雷同色彩的元素相邻,并依照红色、红色、蓝色顺序排列。
此题中,咱们应用整数 0、1 和 2 别离示意红色、红色和蓝色。
示例阐明请见 LeetCode 官网。
起源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权,非商业转载请注明出处。
解法一:遍历数组
首先,申明 2 个参数,zeroIndex 用来记录从左开始第一个不为红色的地位,初始值为 0,twoIndex 用来记录从右开始第一个不为蓝色的地位,初始值为
nums.length - 1
,而后遍历数组,遍历过程如下:
- 如果以后的值等于 2,则将以后地位的值和 twoIndex 地位的值进行替换,而后将 twoIndex 减一,而后进行下一轮解决;
- 如果以后的值等于 1,则持续判断下一个数字;
- 如果以后的值等于 0,则将以后地位的值和 zeroIndex 地位的值进行替换,而后将 zeroIndex 加一,而后进行下一轮解决。
- 遍历完结的地位是 twoIndex,因为 twoIndex 可能会左移,也就是不必遍历到数组的最初一位。
public class LeetCode_075 {public static void sortColors(int[] nums) {if (nums.length == 1) {return;}
// zeroIndex 用来记录从左开始第一个不为红色的地位,twoIndex 用来记录从右开始第一个不为蓝色的地位
int zeroIndex = 0, twoIndex = nums.length - 1;
for (int i = 0; i <= twoIndex;) {if (nums[i] == 2) {
// 如果以后的值等于 2,则将以后地位的值和 twoIndex 地位的值进行替换
nums[i] = nums[twoIndex];
nums[twoIndex] = 2;
twoIndex--;
continue;
} else if (nums[i] == 1) {i++;} else if (nums[i] == 0) {
// 如果以后的值等于 0,则将以后地位的值和 zeroIndex 地位的值进行替换
nums[i] = nums[zeroIndex];
nums[zeroIndex] = 0;
zeroIndex++;
i++;
}
}
}
public static void main(String[] args) {int[] nums = new int[]{2, 0, 2, 1, 1, 0};
sortColors(nums);
for (int num : nums) {System.out.print(num + " ");
}
}
}
【每日寄语】 智者贵于乘时,时不可失。