文档章节

LeetCode:Sort Colors - 对颜色排序(荷兰国旗问题)

北风其凉
 北风其凉
发布于 2016/04/17 22:48
字数 523
阅读 556
收藏 0

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

1、题目名称

Sort Colors(对颜色排序)

2、题目地址

https://leetcode.com/problems/sort-colors/

3、题目内容

英文:

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

中文:

给定一个内含n个由红色、白色和蓝色对象组成的数组,对这些对象进行排序。在本题中,红色用0表示,白色用1表示,蓝色用2表示。

4、解题方法1

虽然题目中的Hint建议你不要使用各个语言提供的Sort类函数解决本问题,但使用Arrays.sort还是可以AC本题的。

Java代码如下:

import java.util.Arrays;

/**
 * 为颜色排序
 * @文件名称 Solution.java
 * @文件作者 Tsybius2014
 * @创建时间 2016年4月16日 上午12:17:49
 */
public class Solution {
    public void sortColors(int[] nums) {
        Arrays.sort(nums);
    }
}

5、解题方法2

后来看了下讨论区,才发现这道题其实考的是“荷兰国旗问题”。

关于“荷兰国旗问题”的描述,可以参考维基百科相关页面:

https://en.wikipedia.org/wiki/Dutch_national_flag_problem

关于“荷兰国旗问题”的解决方法,这篇文章有较为详细的论述:

http://www.cnblogs.com/gnuhpc/archive/2012/12/21/2828166.html

大体思路是使用三个标记begin、curr、end,其中在遍历过程中,begin以前的对象全部是红色的,end以后的对象全部是蓝色的,迭代到最后,begin与end之间的对象一定是白色的。

解题Java代码如下:

/**
 * 为颜色排序
 * @文件名称 Solution.java
 * @文件作者 Tsybius2014
 * @创建时间 2016年4月16日 上午12:17:49
 */
public class Solution {
    public void sortColors(int[] nums) {
        int begin = 0;
        int curr = 0;
        int end = nums.length - 1;
        int temp = 0;
        while (curr <= end) {
            if (nums[curr] == 0) {
                if (begin != curr) {
                    temp = nums[begin];
                    nums[begin] = nums[curr];
                    nums[curr] = temp;
                }
                begin++;
                curr++;
            } else if (nums[curr] == 1) {
                curr++;
            } else if (nums[curr] == 2) {
                if (end != curr) {
                    temp = nums[end];
                    nums[end] = nums[curr];
                    nums[curr] = temp;
                }
                end--;
            }
        }
        
    }
}

END

© 著作权归作者所有

北风其凉

北风其凉

粉丝 121
博文 497
码字总数 462305
作品 4
朝阳
程序员
私信 提问
Leetcode 75. 颜色分类

题目链接 https://leetcode-cn.com/problems/sort-colors/description/ 题目描述 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照...

xgnming
2018/09/06
0
0
算法初级02——荷兰国旗问题、随机快速排序、堆排序、桶排序、相邻两数的最大差值问题、工程中的综合排序算法

主要讨论:荷兰国旗问题、随机快速排序、堆排序、稳定性、比较器、桶排序、相邻两数的最大差值问题和简单介绍工程中的综合排序算法 题目一 给定一个数组arr,和一个数num,请把小于等于num的...

kent鹏
2018/11/12
0
0
LeetCode 75. Sort Colors (颜色排序)

原题 Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blu......

dby_freedom
2018/11/27
0
0
75. Sort Colors - LeetCode

Question 75. Sort Colors Solution 题目大意: 给一个数组排序,这个数组只有0,1,2三个元素,要求只遍历一遍 思路: 记两个索引,lowIdx初始值为0,highIdx初始值为nums.length - 1,遍历数组,如果...

yysue
2018/08/25
25
0
Leetcode【781、869】

问题描述:【Math】781. Rabbits in Forest 解题思路: 森林中的兔子。每个兔子都有颜色,其中一些兔子(可能全部)告诉你还有多少其他的兔子和自己有相同的颜色,将它们的回答放在 answers ...

牛奶芝麻
07/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

有哪些常用的命名git分支实例的例子? [关闭]

现在,我已经使用本地git存储库与我的组的CVS存储库进行了几个月的交互。 我已经制作了一个几乎神经质的分支,其中大部分幸运地合并回我的行李箱。 但是命名开始成为一个问题。 如果我有一个...

javail
18分钟前
5
0
在virtualenv中使用不同的Python版本

我有一个目前使用python 2.5.4运行的Debian系统。 我正确安装了virtualenv,一切正常。 我是否可以将virtualenv与其他版本的Python一起使用? 我编译了Python 2.6.2,并希望将其与一些virtu...

技术盛宴
33分钟前
7
0
保证金术语参考

术语,定义 1.钱包, 余额. ON THE ENCHANGED CONVERGENCE OF STANDARD LATTICE METHODS FOR OPTION PRICING...

MtrS
36分钟前
5
0
x006-函数和模块的使用

函数和模块的使用 在Python中可以使用def关键字来定义函数,和变量一样每个函数也有一个响亮的名字,而且命名规则跟变量的命名规则是一致的。在函数名后面的圆括号中可以放置传递给函数的参数...

伟大源于勇敢的开始
46分钟前
5
0
为什么面试必问线程状态?你的回答满分了吗

看很多同学的面经、网上的面试资料,都不约而同的提到了一个基础问题:“你知道线程有几种状态吗?状态之间的扭转是怎样的?”,有准备的同学都知道有五种:New(新建)、Runnable(可运行)...

Z_J_H
47分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部