2. 考研
  3. 荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。

荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。

admin2012-06-21  126
问题 荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。
选项
答案在算法中设立三个指针，其中，j表示当前元素，i以前的元素全部为红色，k以后的元素全部为蓝色，这样就可以根据j的颜色，把其交换到序列的前部或者后部。算法如下： typedef enum{RED，WHITE，BLUE)color；／／三种颜色 void ColorAErange(color a[]，int n) ／*把由三种颜色组成的序列重排为按照红、白、蓝顺序排序*／ { int i=0； int j=0； int k=n-1： while(j＜=k) { switch(a[j]) { case RED： Swap(a[i]，a[j])；／／交换a[i]，a[j] i++； j++； break； case WHITE； j++； case BLUE； Swap(a[j]，a[k])；／／交换a[k]，a[j] k-／／这里没有j++，防止交换后a[j]仍然是蓝色 } } }
解析
转载请注明原文地址:https://www.kaotiyun.com/show/uAxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)