Coursera Algorithms week2 基础排序 练习测验: Dutch national flag 荷兰国旗问题算法

本文主要是介绍Coursera Algorithms week2 基础排序 练习测验: Dutch national flag 荷兰国旗问题算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

第二周课程的Elementray Sorts部分练习测验Interview Questions的第3题荷兰国旗问题很有意思。题目的原文描述如下:

Dutch national flag. Given an array of n buckets, each containing a red, white, or blue pebble, sort them by color. The allowed operations are:

  • swap(i,j): swap the pebble in bucket i with the pebble in bucket j
  • color(i)determine the color of the pebble in bucket i

The performance requirements are as follows:

  • At most n calls to color()
  • At most n calls to swap()
  • Constant extra space.

该问题在维基百科上的解释为:

The Dutch national flag problem (DNF) is a computer science programming problem proposed by Edsger Dijkstra.The flag of the Netherlands consists of three colors: red, white and blue. Given balls of these three colors arranged randomly in a line (the actual number of balls does not matter), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order.

 

本题的限制条件n calls to color()意味着每个元素最多只能访问一次,也就是要求在遍历一次所有元素的情况下完成排序。遍历结束时红色球要全部在数组的左侧,白色球全部在中间,蓝色球全部在右侧,整个数组将被分成三部分。用current记录当前需要访问的球的位置,还需要两个位置记录红-白分界处和白-蓝分界处,用lo来标记白色球的开始位置,hi来标记白色球的结束位置。lo和current起始相同,两个从数组左侧以++方式前进,hi从数组右侧以--方式前进。循环主体设计方式:【后来看到3way-quicksort,发现这个做法与3way-quicksort很像,而且后者代码更清晰简单,特在文末附了3way-quicksort的实现】

1、当current为红色时,如果lo==current,不需要交换位置,二者均前进++一步;如果不相等,意味着current 肯定大于lo,lo和current之间都为白色球,将lo和current位置处的球进行交换,lo处就变成了红色球,current处就变成了白色球,lo需要++前进一步来标志白色球的起始位置,而此时current处的球在之前已经被遍历过(左侧的球均被遍历过),current也需要++前进一步来访问下一个球

2. 当current为白色时,该球位置正确,不需要移动,current直接++前进一步

3. 当current为蓝色时,表明该球应该放置于数组右侧,此时需要和数组右侧hi处的球交换,然后hi处的球就变成了蓝色,并且该蓝色球是已经被访问过的,hi需要往右侧--前进。而此时current处交换过来的球还没有被访问过,故current位置不需要变动,留到下一次循环进行访问。

循环体在current访问完所有的球后结束,也就是current>hi时结束,因为大于hi的节点都是由current遍历交换过来的。

 

 

 

代码实现:

 1 import java.util.Arrays;
 2 import edu.princeton.cs.algs4.StdRandom;
 3 
 4 public class DutchNationalFlag {
 5     public static final int RED = 0;
 6     public static final int WHITE = 1;
 7     public static final int BLUE = 2;
 8     private int n;
 9     private int[] buckets;
10     public int callColorNum = 0;
11     public int callSwapNum = 0;
12 
13     public DutchNationalFlag(int[] buckets) {
14         n = buckets.length;
15         this.buckets = buckets;
16     }
17 
18     public void sort() {
19         int lo = 0;
20         int hi = n - 1;
21         int current = lo;
22         while (current <= hi) {
23             switch(color(current)){
24             case RED:
25                 if (current != lo) 
26                     swap(current, lo);
27                 current++;
28                 lo++;
29                 break;
30             case WHITE:
31                 current++;
32                 break;
33             case BLUE:
34                 swap(hi,current);
35                 hi--;
36                 break;
37             }
38         }
39     }
40 
41     private void swap(int i, int j) {
42         callSwapNum++;
43         int t = buckets[i];
44         buckets[i] = buckets[j];
45         buckets[j] = t;
46     }
47 
48     private int color(int i) {
49         callColorNum ++;
50         return buckets[i];
51     }
52 
53     public static void main(String[] args) {
54         int n = 10;
55         int[] buckets = new int[n];
56         for (int i = 0; i < n; i++) {
57             buckets[i] = StdRandom.uniform(3);
58         }
59         System.out.println(Arrays.toString(buckets));
60         DutchNationalFlag dnf = new DutchNationalFlag(buckets);
61         dnf.sort();
62         System.out.println("after sort call color+"+dnf.callColorNum+"times, call swap="+ dnf.callSwapNum+"times");
63         System.out.println(Arrays.toString(buckets));
64     }
65 }

 

思路参考http://www.cnblogs.com/gnuhpc/archive/2012/12/21/2828166.html

 

3way-quicksort实现:

 1     public void quickSort3way(){
 2         int lt = 0;
 3         int gt = n - 1;
 4         int i = 0;
 5         while (i <= gt) {
 6             int cc = color(i);
 7             if(cc < WHITE) swap(lt++,i++);
 8             else if(cc > WHITE) swap(i,gt--);
 9             else i++;
10         }
11     }

 

转载于:https://www.cnblogs.com/evasean/p/7217623.html

这篇关于Coursera Algorithms week2 基础排序 练习测验: Dutch national flag 荷兰国旗问题算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/647246

相关文章

从基础到进阶详解Pandas时间数据处理指南

《从基础到进阶详解Pandas时间数据处理指南》Pandas构建了完整的时间数据处理生态,核心由四个基础类构成,Timestamp,DatetimeIndex,Period和Timedelta,下面我... 目录1. 时间数据类型与基础操作1.1 核心时间对象体系1.2 时间数据生成技巧2. 时间索引与数据

MySQL 设置AUTO_INCREMENT 无效的问题解决

《MySQL设置AUTO_INCREMENT无效的问题解决》本文主要介绍了MySQL设置AUTO_INCREMENT无效的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参... 目录快速设置mysql的auto_increment参数一、修改 AUTO_INCREMENT 的值。

关于跨域无效的问题及解决(java后端方案)

《关于跨域无效的问题及解决(java后端方案)》:本文主要介绍关于跨域无效的问题及解决(java后端方案),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录通用后端跨域方法1、@CrossOrigin 注解2、springboot2.0 实现WebMvcConfig

Go语言中泄漏缓冲区的问题解决

《Go语言中泄漏缓冲区的问题解决》缓冲区是一种常见的数据结构,常被用于在不同的并发单元之间传递数据,然而,若缓冲区使用不当,就可能引发泄漏缓冲区问题,本文就来介绍一下问题的解决,感兴趣的可以了解一下... 目录引言泄漏缓冲区的基本概念代码示例:泄漏缓冲区的产生项目场景:Web 服务器中的请求缓冲场景描述代码

Java死锁问题解决方案及示例详解

《Java死锁问题解决方案及示例详解》死锁是指两个或多个线程因争夺资源而相互等待,导致所有线程都无法继续执行的一种状态,本文给大家详细介绍了Java死锁问题解决方案详解及实践样例,需要的朋友可以参考下... 目录1、简述死锁的四个必要条件:2、死锁示例代码3、如何检测死锁?3.1 使用 jstack3.2

解决JSONField、JsonProperty不生效的问题

《解决JSONField、JsonProperty不生效的问题》:本文主要介绍解决JSONField、JsonProperty不生效的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录jsONField、JsonProperty不生效javascript问题排查总结JSONField

github打不开的问题分析及解决

《github打不开的问题分析及解决》:本文主要介绍github打不开的问题分析及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、找到github.com域名解析的ip地址二、找到github.global.ssl.fastly.net网址解析的ip地址三

MySQL版本问题导致项目无法启动问题的解决方案

《MySQL版本问题导致项目无法启动问题的解决方案》本文记录了一次因MySQL版本不一致导致项目启动失败的经历,详细解析了连接错误的原因,并提供了两种解决方案:调整连接字符串禁用SSL或统一MySQL... 目录本地项目启动报错报错原因:解决方案第一个:第二种:容器启动mysql的坑两种修改时区的方法:本地

springboot加载不到nacos配置中心的配置问题处理

《springboot加载不到nacos配置中心的配置问题处理》:本文主要介绍springboot加载不到nacos配置中心的配置问题处理,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录springboot加载不到nacos配置中心的配置两种可能Spring Boot 版本Nacos

安装centos8设置基础软件仓库时出错的解决方案

《安装centos8设置基础软件仓库时出错的解决方案》:本文主要介绍安装centos8设置基础软件仓库时出错的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录安装Centos8设置基础软件仓库时出错版本 8版本 8.2.200android4版本 javas