如何实现LeetCode 75题中的颜色排序算法？
- 内容介绍
- 文章标签
- 相关推荐
本文共计893个文字，预计阅读时间需要4分钟。
使用常规思路思路解决或根据题目限定条件确定的一种思路。例如，LeetCode 75. Sort Colors 颜色分类，题目大意+链接：https://leetcode.cn/problems/sort-colors/。给定一个包含红色、白色和蓝色，共 n 个元素的数组，原地对它们进行排序。
具体思路如下：
1.遍历数组，对于每个元素，根据其颜色进行分类。
2.使用三个指针，分别指向红、白、蓝元素的末尾。
3.从左到右遍历数组，将红、白、蓝元素分别放到对应的指针位置，并移动指针。
示例代码：
pythondef sortColors(nums): n=len(nums) red, white, blue=0, 0, n - 1 while white <=blue: if nums[white]==0: nums[red], nums[white]=nums[white], nums[red] red +=1 white +=1 elif nums[white]==1: white +=1 else: nums[white], nums[blue]=nums[blue], nums[white] blue -=1 使用常规思路桶排序解决或根据题目限定条件的另一种思路，leetcode 75. Sort Colors 颜色分类 一、题目大意链接：leetcode.cn/problems/sort-colors
给定一个包含红色、白色和蓝色、共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
进阶：
- 你可以不使用代码库中的排序函数来解决这道题吗？
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
两个思路，一是用桶排序，先统计频率，再按key排序，最后提取结果。另一种思路，因为值的话就3个是已经确定的，遍历数组0往数组最左边放，2往最右边放，遍历完数组就排好了。
三、解题方法 3.1 Java实现-桶排序public class Solution {
public void sortColors(int[] nums) {
// 统计频率
Map<Integer, Integer> seqMap = new HashMap<>();
for (int tmp : nums) {
seqMap.put(tmp, seqMap.getOrDefault(tmp, 0) + 1);
}
// 按key排序
PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue = new PriorityQueue<>((a, b) -> b.getKey() - a.getKey());
for (Map.Entry<Integer, Integer> entry : seqMap.entrySet()) {
priorityQueue.add(entry);
}
// 提取结果
int idx = nums.length - 1;
while (!priorityQueue.isEmpty()) {
Map.Entry<Integer, Integer> entry = priorityQueue.poll();
for (int i = 0; i < entry.getValue(); i++) {
nums[idx--] = entry.getKey();
}
}
}
}
3.2 Java实现-另一种思路
public class Solution2 {
public void sortColors(int[] nums) {
int left = 0;
int right = nums.length - 1;
// 注意结束条件是 i<=right
for (int i = 0; i <= right; i++) {
if (nums[i] == 0) {
swap(nums, i, left++);
} else if (nums[i] == 2) {
// 注意此时i要呆在原地，因为for里面会执行i++,此时做i--做消减
swap(nums, i--, right--);
}
}
}
void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
四、总结小记
- 2022/5/24 用固定的套路桶排序解题耗时2毫秒，用另一种思路耗时不到1毫秒，虽然耗时少但我们还要掌握固定套路。
本文共计893个文字，预计阅读时间需要4分钟。
使用常规思路思路解决或根据题目限定条件确定的一种思路。例如，LeetCode 75. Sort Colors 颜色分类，题目大意+链接：https://leetcode.cn/problems/sort-colors/。给定一个包含红色、白色和蓝色，共 n 个元素的数组，原地对它们进行排序。
具体思路如下：
1.遍历数组，对于每个元素，根据其颜色进行分类。
2.使用三个指针，分别指向红、白、蓝元素的末尾。
3.从左到右遍历数组，将红、白、蓝元素分别放到对应的指针位置，并移动指针。
示例代码：
pythondef sortColors(nums): n=len(nums) red, white, blue=0, 0, n - 1 while white <=blue: if nums[white]==0: nums[red], nums[white]=nums[white], nums[red] red +=1 white +=1 elif nums[white]==1: white +=1 else: nums[white], nums[blue]=nums[blue], nums[white] blue -=1 使用常规思路桶排序解决或根据题目限定条件的另一种思路，leetcode 75. Sort Colors 颜色分类 一、题目大意链接：leetcode.cn/problems/sort-colors
给定一个包含红色、白色和蓝色、共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
进阶：
- 你可以不使用代码库中的排序函数来解决这道题吗？
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
两个思路，一是用桶排序，先统计频率，再按key排序，最后提取结果。另一种思路，因为值的话就3个是已经确定的，遍历数组0往数组最左边放，2往最右边放，遍历完数组就排好了。
三、解题方法 3.1 Java实现-桶排序public class Solution {
public void sortColors(int[] nums) {
// 统计频率
Map<Integer, Integer> seqMap = new HashMap<>();
for (int tmp : nums) {
seqMap.put(tmp, seqMap.getOrDefault(tmp, 0) + 1);
}
// 按key排序
PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue = new PriorityQueue<>((a, b) -> b.getKey() - a.getKey());
for (Map.Entry<Integer, Integer> entry : seqMap.entrySet()) {
priorityQueue.add(entry);
}
// 提取结果
int idx = nums.length - 1;
while (!priorityQueue.isEmpty()) {
Map.Entry<Integer, Integer> entry = priorityQueue.poll();
for (int i = 0; i < entry.getValue(); i++) {
nums[idx--] = entry.getKey();
}
}
}
}
3.2 Java实现-另一种思路
public class Solution2 {
public void sortColors(int[] nums) {
int left = 0;
int right = nums.length - 1;
// 注意结束条件是 i<=right
for (int i = 0; i <= right; i++) {
if (nums[i] == 0) {
swap(nums, i, left++);
} else if (nums[i] == 2) {
// 注意此时i要呆在原地，因为for里面会执行i++,此时做i--做消减
swap(nums, i--, right--);
}
}
}
void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
四、总结小记
- 2022/5/24 用固定的套路桶排序解题耗时2毫秒，用另一种思路耗时不到1毫秒，虽然耗时少但我们还要掌握固定套路。