一、题目大意
链接：https://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毫秒，虽然耗时少但我们还要掌握固定套路。
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
