【LeetCode】75-颜色分类
2024-09-01 07:34:40
题目描述
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶:
- 一个直观的解决方案是使用计数排序的两趟扫描算法。
首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。 - 你能想出一个仅使用常数空间的一趟扫描算法吗?
解题思路
这一题实际上就是经典的荷兰国旗问题:
我们将乱序的红白蓝三色小球排列成有序的红白蓝三色的同颜色在一起的小球组。这个问题之所以叫荷兰国旗,是因为我们可以将红白蓝三色小球想象成条状物,有序排列后正好组成荷兰国旗。
注意,这个问题最后要求最后的结果是有序排列的,就这一题来说,最后的结果必须是[0,0,1,1,2,2]
这种形式的,而不能是[1,1,0,0,2,2]
这种顺序不对的。
从左到右遍历一遍数组,使用三个指针,left
,right
和current
,其中left
使得nums[l0...left-1]
中的元素都小于v
,right
使得nums[right+1...hi]
中的元素都大于v
,current
使得nums[left...current-1]
中的元素都等于v
。在遍历过程中:
nums[current] < v
,将nums[left]
和nums[current]
交换,将left
和current
加一nums[current] > v
,将nums[right]
和nums[current]
交换,将right
减一nums[current] = v
,将i
加一
Java 实现
class Solution {
public void sortColors (int[] nums) {
sort(nums, 0, nums.length - 1);
}
private static void sort (int[] nums, int lo, int hi) {
if (hi <= lo) return;
int left = lo, current = lo + 1, right = hi;
int v = nums[lo];
while (current <= right) {
if (nums[current] < v) exch(nums, left++, current++);
else if (nums[current] > v) exch(nums, current, right--);
else current++;
}
sort(nums, lo, left - 1);
sort(nums, right + 1, hi);
}
private static void exch (int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
心得体会
这一题结合快速排序中的相关知识就比较好理解了
一个集合中含有大量重复元素时,使用三向切分快速排序比经典的快速排序更有效率,因为它避免将一个有很多重复的子集继续切分为更小的子集
参考:《算法》第四版,187页,2.3.3.3 熵最优的排序
最新文章
- 架设lamp服务器后,发现未按照 Apache xsendfile模块,
- iOS使用keychain存储密码
- Java SAX DefaultHandler
- BZOJ3156: 防御准备
- 学习iOS必须知道的[转载]
- Java中的枚举类型详解
- JQuery 限制文本框只能输入数字和小数点
- 一种用javascript实现的比较兼容的回到顶部demo + 阻止事件冒泡
- ";浏览器端"; 使用 commonjs 模块规范开发网页应用,像开发 node 那样开发网页应用
- JavaEE开发之SpringBoot整合MyBatis以及Thymeleaf模板引擎
- 浅论Javascript在汽车信号测试中的应用
- UIPopoverPresentationController使用
- LeetCode 455. Assign Cookies (分发曲奇饼干)
- Netty入门之HelloWorld
- MySQL数据库存储过程动态表建立(PREPARE)
- java泛型基础、子类泛型不能转换成父类泛型
- maven 转myeclipse eclipse 项目 命令
- 简单了解一下php的迭代生成器yield
- kafka 配置文件注释
- 【codeforces】【比赛题解】#849 CF Round #431 (Div.2)