这篇文章主要为大家展示了“LeetCode如何实现颜色分类”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“LeetCode如何实现颜色分类”这篇文章吧。
一,颜色分类
1,问题简述
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
进阶:
你可以不使用代码库中的排序函数来解决这道题吗?你能想出一个仅使用常数空间的一趟扫描算法吗?
2,示例描述
示例 1:
输入:nums = [2,0,2,1,1,0]
输出:[0,0,1,1,2,2]
示例 2:
输入:nums = [2,0,1]
输出:[0,1,2]
示例 3:
输入:nums = [0]
输出:[0]
示例 4:
输入:nums = [1]
输出:[1]
提示:
n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2
3,题解思路
基于双指针的思路进行实现,基于键值对集合进行实现
4,题解程序
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.Map;
public class SortColorsTest2 {
public static void main(String[] args) {
int[] nums = {2, 0, 2, 1, 1, 0};
sortColors(nums);
System.out.println();
for (int num : nums) {
System.out.print(num + "/t");
}
}
public static void sortColors(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
int left = 0;
int right = nums.length - 1;
for (int i = 0; i <= right; ) {
if (nums[i] == 0) {
int temp = nums[left];
nums[left] = nums[i];
nums[i] = temp;
++left;
++i;
} else if (nums[i] == 2) {
int temp = nums[right];
nums[right] = nums[i];
nums[i] = temp;
--right;
} else {
++i;
}
}
}
public static void sortColors2(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
Arrays.sort(nums);
Map<Integer, Integer> map = new LinkedHashMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
Arrays.fill(nums, 0);
int[] result = new int[nums.length];
int index = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
Integer value = entry.getValue();
while (value > 0) {
result[index++] = entry.getKey();
value--;
}
}
System.arraycopy(result, 0, nums, 0, result.length);
}
}
以上是“LeetCode如何实现颜色分类”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!
原创文章,作者:kirin,如若转载,请注明出处:https://blog.ytso.com/223625.html