【算法hot100】颜色分类(75)
算法 分类 颜色 75
2023-09-27 14:29:28 时间
颜色分类(75)
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。
示例 1:
输入:nums = [2,0,2,1,1,0]
输出:[0,0,1,1,2,2]来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解法一:
public class LC020_75_sortColors_01 {
public static void main(String[] args) {
int[] nums = new int[]{2, 0, 2, 1, 1, 0};
sortColors(nums);
}
public static void sortColors(int[] nums) {
Arrays.sort(nums);
}
}
解法二:
public class LC020_75_sortColors_02 {
public static void main(String[] args) {
int[] nums = new int[]{2, 0, 2, 1, 1, 0};
sortColors(nums);
}
public static void sortColors(int[] nums) {
int index = 0;
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
if (num == 0) {
swap(nums, i, index);
index++;
}
}
for (int i = index; i < nums.length; i++) {
int num = nums[i];
if (num == 1) {
swap(nums, i, index);
index++;
}
}
}
public static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
解法三:
public class LC020_75_sortColors_03 {
public static void main(String[] args) {
int[] nums = new int[]{2, 0, 2, 1, 1, 0};
sortColors(nums);
}
public static void sortColors(int[] nums) {
int index1 = 0, index2 = 0;
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
if (num == 1) {
swap(nums, i, index2);
index2++;
} else if (num == 0) {
swap(nums, i, index1);
if (index1 < index2) {
swap(nums, i, index2);
}
index1++;
index2++;
}
}
}
public static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
解法四:
public class LC020_75_sortColors_04 {
public static void main(String[] args) {
int[] nums = new int[]{2, 0, 2, 1, 1, 0};
sortColors(nums);
}
public static void sortColors(int[] nums) {
int n = nums.length;
int left = 0, right = n - 1;
for (int i = 0; i < n; i++) {
while (nums[i] == 2 && i <= right) {
swap(nums, i, right);
right--;
}
if (nums[i] == 0) {
swap(nums, i, left);
left++;
}
}
}
public static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
相关文章
- 死磕程序员必备算法:递归!
- 机器学习-分类算法-kNN
- 基于深度学习的步态识别算法的MATLAB仿真
- 机器学习面试题——KNN(K Nearest Neighbors)K近邻分类算法
- 程序实现蒙特卡洛算法计算PI值和积分
- 数据结构经典算法
- 时间轮算法(TimingWheel)是如何实现的?
- 《数据挖掘:理论与算法》学习笔记(四)—贝叶斯分类
- DCT(离散余弦变换)算法原理和源码
- 朴素贝叶斯分类算法简述
- 《写给程序员的数据挖掘实践指南》——第5章 分类的进一步探讨—算法评估及kNN
- 《实用机器学习》——1.2 机器学习算法的分类
- ANSI X9.19 MAC算法
- 《高性能科学与工程计算》——3.5 算法分类和访存优化
- 《数据结构与算法 C语言版》—— 1.8小结
- 【转载】 优必选悉尼 AI 研究院何诗怡:基于课程学习的强化多标签图像分类算法 | 分享总结
- java学习-AES加解密之AES-128-CBC算法
- 浅析分布式一致性算法 - Raft算法:定义、为什么需要一致性、强/弱一致性分类区别、raft三种状态、领导选举算法流程、日志复制流程、安全选举限制、如何解决split brain的问题
- 算法复习笔记(二)蛮力法
- AI学习---分类算法[K-近邻 + 朴素贝叶斯 + 决策树 + 随机森林 ]
- Java的递归算法
- Python算法:随机森林分类
- Python算法:决策树分类
- C/C++ 八大排序算法