-
2020-06-19 13:51:52
题目描述
现在有一个包含n个物体的数组,其中物体颜色为颜色为红色、白色或蓝色,请对这个数组进行排序,让相同颜色的物体相邻,颜色的顺序为红色,白色,蓝色。
我们用0,1,2分别代表颜色红,白,蓝
注意:
给出一个只用一步,并且能在常数级空间复杂度解决这个问题的算法吗?
思路:荷兰国旗算法 即最终将序列分为三部分 小于1 等于1 大于1
初始化 P_0=0表示小部分的右起点 P_2=size-1表示大部分的右起点
开始从前往后遍历
若该数小于1 那么A[i]与A[P_0]作交换 相当于把小的数踢到前面,同时i++
若该数大于1 那么A[i]与A[P_2]作交换 相当于把大的数移动到最后 注意此时i不变
(因为交换到A[i]的数字可能是0 是 1 是 2需要进一步放到合适的位置)
若该数等于1 不作任何处理 跳过即 i++
(循环的条件是 i<P_2+1 因为到达2所在部分 继续执行会把 2与之前的1 或 0作交换 使得序列出错)
void sortColors(int A[], int n) { if(n==0) return; //三路快排思路 交换原理 int p_0=0; //0元素部分从0位置开始 int p_2=n-1;// 2元素部分从最后一个位置往前放 int i=0; while(i<p_2+1) { if(A[i]==0) //属于第一部分 { int tmp=A[p_0]; A[p_0]=A[i]; A[i]=tmp; p_0++; // 将0元素踢到前面 两者交换即可 i++; } else if(A[i]==2) { int tmp=A[p_2]; A[p_2]=A[i]; A[i]=tmp; p_2--; // 将2元素踢到后面 两者交换即可 } else //A[i]=1 不做任何处理 跳过 { i++; } } }
更多相关内容 -
荷兰国旗系列问题
2021-01-07 08:05:58问题:给定一个数组arr和一个数字num,请把小于num的数放在数组的左边,等于num的数放在数组的中间,大于num的数放在数组的右边。 要求额外空间复杂度O(1),时间复杂度O(N) #include using namespace std; void ... -
C解决荷兰国旗问题
2017-07-10 20:10:29学生作业:C语言解决荷兰国旗问题。小程序。 -
荷兰国旗问题
2012-10-14 13:32:06荷兰国旗问题 数据结构学习 算法设计与分析学习 -
荷兰国旗问题以及快速排序
2021-11-27 20:04:021、啥是荷兰国旗问题荷兰国旗是由红白蓝3种颜色的条纹拼接而成,如下图所示:假设这样的条纹有多条,且各种颜色的数量不一,并且随机组成了一个新的图形,新的图形可能如下图所示,但不仅仅只有这一种情况:需求是:...大家好,我是周一。
最近几篇算法,我们都是聊的归并排序,归并排序也说的差不多了,今天讲讲快速排序。
一、荷兰国旗问题
1、啥是荷兰国旗问题
荷兰国旗是由红白蓝3种颜色的条纹拼接而成,如下图所示:
假设这样的条纹有多条,且各种颜色的数量不一,并且随机组成了一个新的图形,新的图形可能如下图所示,但不仅仅只有这一种情况:
需求是:把这些条纹按照颜色排好,红色的在上半部分,白色的在中间部分,蓝色的在下半部分,我们把这类问题称作荷兰国旗问题。
2、荷兰国旗问题的抽象
我们把荷兰国旗问题抽象成数组的形式是下面这样的:
给定一个整数数组和一个值M(存在于原数组中),要求把数组中小于M的元素放到数组的左边,等于M的元素放到数组的中间,大于M的元素放到数组的右边,最终返回一个整数数组,只有两个值,0位置是等于M的数组部分的左下标值、1位置是等于M的数组部分的右下标值。
进一步抽象为更加通用的形式是下面这样的:
给定数组arr,将[l, r]范围内的数(当然默认是 [ 0 - arr.length - 1 ]),小于arr[r](这里直接取数组最右边的值进行比较)放到数组左边,等于arr[r]放到数组中间,大于arr[r]放到数组右边。最后返回等于arr[r]的左, 右下标值。
3、解决的思路
定义一个小于区,一个大于区;遍历数组,挨个和arr[r]比较,
(1)小于arr[r],与小于区的后一个位置交换,当前位置后移;
(2)等于arr[r],当前位置直接后移;
(3)大于arr[r],与大于区的前一个位置交换,当前位置不动(交换到此位置的数还没比较过,所以不动)。
遍历完后,arr[r]和大于区的最左侧位置交换。
最后返回,此时小于区的后一个位置,大于区的位置,即是最后的等于arr[r]的左, 右下标值。
4、详细的参考代码
/** * 荷兰国旗问题 * <p> * 把数组arr中,[l, r]范围内的数,小于arr[r]放到数组最左边,等于arr[r]放到数组中间,大于arr[r]放到数组最右边 * * @return 返回等于arr[r]的左, 右下标值 */ public static int[] netherlandsFlag(int[] arr, int l, int r) { if (l > r) { return new int[]{-1, -1}; } if (l == r) { return new int[]{l, r}; } // 小于arr[r]的右边界,从L的左边一位开始 int less = l - 1; // 大于arr[r]的左边界,从r开始,即当前右边界里已经有arr[r] int more = r; // 当前正在比较的下标 int index = l; // 不能与 大于arr[r]的左边界 撞上 while (index < more) { if (arr[index] < arr[r]) { // 小于时,将当前位置的数和小于arr[r]的右边界的下一个位置交换 // 当前位置后移一位 swap(arr, index++, ++less); } else if (arr[index] == arr[r]) { // 等于时,当前位置后移一位即可 index++; } else { // 大于时,当前位置的数和大于arr[r]的左边界的前一个位置交换 // 当前位置不动 swap(arr, index, --more); } } // 将arr[r]位置的数和大于arr[r]的左边界的数交换 // 此时整个数组就按照 小于、等于、大于arr[r] 分成了左中右三块 swap(arr, more, r); // 最后整个数组中,等于arr[r]的左右边界分别是less + 1, more return new int[]{less + 1, more}; }
二、快速排序
1、啥是快排(排序流程)
首先设定一个分界值,通过该分界值将数组分成左中右三部分。
(1)将小于分界值的数据集中到数组的左边,等于分界值的数据集中到数组的中间,大于分界值的数据集中到数组右边。
(2)然后,左边和右边的数据可以独立排序。对于左侧的数据,又可以取一个分界值,将该部分数据分成左中右三部分,同样在左边放较小值,中间放等于值,右边放较大值。右边数据也做同样的处理。
(3)重复上述过程,可以看出,这是一个递归过程。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。
当看完了快排的流程,是不是发现快排的核心方法就是荷兰国旗问题,所以知道为啥本文一开始就介绍荷兰国旗问题了吧。
2、抽象后的快排流程
(1)随机将数组中的某个数放到比较位置上(即最右侧位置)
(2)调用荷兰国旗方法,(此时等于区的数即在最后排好序的位置上),拿到等于区的左右下标
(3)小于区和大于区再各自递归调用(1)(2)步即可将小于区和大于区排好序。
3、详细的参考代码
/** * 随机快排 */ public static void quickSortRandom(int[] arr) { if (arr == null || arr.length < 2) { return; } processRandom(arr, 0, arr.length - 1); } private static void processRandom(int[] arr, int l, int r) { if (l >= r) { return; } // 随机将数组中的某个数放到比较位置上(即数组最右边位置) // 这一步是保证快排时间复杂度是O(N*logN)的关键,不然,快排的时间复杂度是O(N^2) swap(arr, l + (int) ((r - l + 1) * Math.random()), r); // 将数组划分为 小于、等于、大于arr[r] 的左中右三块 int[] equalArea = netherlandsFlag(arr, l, r); // 此时等于区域的值已经处于最后排序结果的位置了 // 递归将左半部分的排好序 processRandom(arr, l, equalArea[0] - 1); // 递归将右半部分的排好序 processRandom(arr, equalArea[1] + 1, r); } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
-
C/C++实现荷兰国旗问题
2021-01-23 15:13:34荷兰国旗问题 给定一个数组arr,和一个数num,请把小于num的数放在数组的左边,等于num的数放在数组的中间,大于num的数放在数组的右边 要求额外空间复杂度O(1),时间复杂度O(N) 思路 使用两个指针来标记小于num...荷兰国旗问题
给定一个数组arr,和一个数num,请把小于num的数放在数组的左边,等于num的数放在数组的中间,大于num的数放在数组的右边
要求额外空间复杂度O(1),时间复杂度O(N)思路
使用两个指针来标记小于num部分和大于num部分
less指向小于num部分最后一位
more指向大于num部分的第一位
cur指向当前位置
分三种情况:
(1)当arr[cur] > num时,交换arr[cur] 和 arr[–more],cur保持不变
(2)当arr[cur] < num时,交换arr[cur]和arr[++less],cur++
(3)当arr[cur] = num时,cur++代码
#include <bits/stdc++.h> using namespace std; inline void swap(int arr[], int i, int j); int* partition(int arr[], int L, int R, int num){ int less = L-1; int more = R+1; int cur = L; while(cur < more){ if(arr[cur] > num){ swap(arr, --more, cur); }else if (arr[cur] < num){ swap(arr, ++less, cur++); }else{ cur++; } } return new int [2] {less, more}; } inline void swap(int arr[], int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } inline void outputArr(int arr[], int L, int R){ for(int i = L; i <= R; i++){ cout << arr[i] << " "; } cout << endl; } int main(){ int num; int arr[10] = {2,4,8,9,4,3,2,1,6,8}; int *result; cin >> num; outputArr(partition(arr, 0, 9, num), 0, 1); outputArr(arr, 0, 9); }
相关问题
荷兰国旗问题是实现快速排序的基本思想,对于理解快速排序有重要意义
快速排序的实现可以参考这篇文章:
随机快速排序 -
荷兰国旗问题(C语言)
2022-04-20 09:41:46荷兰国旗问题 简化版荷兰国旗问题 给定一个数组arr,和一个数num,请把小于等于num的数放在数组的左边,大于num的数放在数组的右边。要求额外空间复杂度O(1),时间复杂度O(N)。 void swap(int *a, int *b) { int ...荷兰国旗问题
- 简化版荷兰国旗问题
给定一个数组arr,和一个数num,请把小于等于num的数放在数组的左边,大于num的数放在数组的右边。要求额外空间复杂度O(1),时间复杂度O(N)。
void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } void process(int *a[], int num) { int i = 0; int p1 = -1; while (i < 8) { if (a[i] <= num) { swap(&a[i], &a[p1 + 1]); i++; p1++; } else i++; } } int main() { int a[8] = {3, 5, 6, 7, 4, 3, 5, 8}; int num = 5; process(&a, num); for (int i = 0; i < 8; i++) printf("%d", a[i]); return 0; }
这里举的例子是3,5,6,7,4,3,5,8
左 中 右 <=num >num 待定 这相当一个一个从左到右的推进。p1指向左,i指向待定区域的开始,然后i向右推进,碰到>num的不做处理,i++,如果碰到<=num的,将i指向的这个符合条件的元素和最靠近左区域的数,也就是中区域最左边的数交换,这样中区域最左边的数就符合<=num,然后i++,p++。
本质是左区域推着中区域向右,最终判断完所有的待定区域。
- 真荷兰国旗问题
给定一个数组arr,和一个数num,请把小于num的数放在数组的左边,等于num的数放在数组的中间,大于num的数放在数组的右边,要求额外空间复杂度O(1),时间复杂度O(N)。
#include <stdio.h> void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } void process(int *a[], int flag) { int i = 0; int p1 = -1; int p2 = 10;//这里直接赋了一个具体的数,本来用sizeof(a)来求,却有bug while (i < p2)//注意sizeof(a)在这里得到的并不是一个数组的长度,而是一个元素的长度。 { if (a[i] < flag) { swap(&a[i], &a[p1 + 1]); p1++; i++; } else if (a[i] == flag) { i++; } else { swap(&a[i], &a[p2 - 1]); p2--; } } } int main() { int a[10] = {3, 5, 6, 3, 4, 5, 2, 6, 9, 0}; int flag = 5; process(&a, flag); for (int i = 0; i < 10; i++) { printf("%d,", a[i]); } return 0; }
< = 待定 > p1 i p2 真正的荷兰国旗问题,多了右边向左的推进,同时注意,i只向右推进,因为i左边的数都被遍历过,所以对于<num可以进行i++,而>num再交换数之后,不能有i++,因为此时i指向的数是右边交换过来的新数,没有经过遍历,所以i不动。
荷兰国旗问题中的i变化,根据不同情况将数变动至<num和>num区域的思想能跟很好地契合进快排算法中去,具体内容见下一篇博客。
感谢你能看到这里,祝好。
-
算法:快速排序与荷兰国旗问题
2021-09-22 19:00:14文章目录荷兰国旗算法描述荷兰国旗代码展示快排算法描述快排代码展示 在聊快速排序之前,我们先解释一下荷兰国旗,即把一个数组分成三个部分,我们一般选最后一个元素作为基准值,即大于这个数的全部在左边,小于这... -
数据结构与算法Java版-荷兰国旗问题
2021-07-17 18:34:44荷兰国旗问题 荷兰国旗是由红白蓝3种颜色的条纹拼接而成,如下图所示: 假设这样的条纹有多条,且各种颜色的数量不一,并且随机组成了一个新的图形,新的图形可能如下图所示,但是绝非只有这一种情况: 需求是:把... -
python实现荷兰国旗问题
2019-07-15 11:27:21问题描述: 荷兰国旗仅有红、白、蓝三色构成。设有一个仅有红、白、蓝三种颜色的n个条块组成的条块序列,请设计一个时间复杂度为O(n)的算法使得这些红、白、蓝的顺序排好,也就是构成荷兰国旗的。 问题分析: 这个... -
荷兰国旗问题(分三块)
2020-02-22 22:03:03——堆排序扩展问题 已知一个几乎有序的数组,几乎有序是指,如果把数组排好序的话,每个元素移动的距离可以不超过k,并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。 分析: 假设k的... -
荷兰国旗问题java
2017-03-01 10:38:28public class HollandFlagProblem { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] A = { 2, 0, 2, 0, 0, 2, 1, 1, 0, 2, 1, 0, 1, 2, 0, 1 -
Leetcode 题解 -- 排序--荷兰国旗问题
2019-05-16 10:16:43荷兰国旗问题 1.暴力解法 记录每个的个数 2. 双指针 中间的 荷兰国旗包含三种颜色:红、白、蓝。 有三种颜色的球,算法的目标是将这三种球按颜色顺序正确地排列。 它其实是三向切分快速排序的一种变种,在三向... -
荷兰国旗问题(partition)总结
2019-04-14 23:57:35partition算法,又称为荷兰国旗问题,其主要包括两个问题。 1 问题1-二分partition 给定一个数组a和一个数n,把小于等于n的数字放在数组的左边,大于n的数放在数组的右边,要求额外空间复杂度O(1),时间复杂度O(n) ... -
Java实现荷兰国旗问题
2019-07-21 22:04:45这个问题之所以叫荷兰国旗,是因为将红白蓝三色的小球弄成条状物,并有序排列后正好组成荷兰国旗。 2 解决方案 为了方便编码与讨论,用数字0表示红球,数字1表示白球,数字2表示蓝球,所以最后生成的排列为0,1,2。 ... -
关于 (基础)荷兰国旗 问题的 C语言实现----》引出后续 快速排序 问题
2022-02-08 21:16:29荷兰国旗问题1.0 题目描述: 给定一个 无序的数组 和 一个数num,要求最终该数组 左侧为<=num的数,右侧为>num的数,左右侧的数不用有序。 当然了,该题有很多解法,但可能你第一时间想到的是再创建一个... -
C语言实例——荷兰国旗问题
2020-03-29 17:20:37C语言实例——荷兰国旗问题 问题描述: 要求重新排列一个由字符R,W,B(R代表红色,W代表白色,B代表蓝色)构成的数组,使得所有的R都排在最前面,W排在其后,B排在最后。 解决思路: 问题实质为对一个字符数组重新... -
荷兰国旗问题的C++实现
2013-03-04 01:04:06设有一个仅由红、白、蓝三种颜色的条块组成的序列。试设计一个时间复杂度为O(n)的算法,使得这些条块按红、白、蓝的顺序排好,即排成荷兰国旗图案。 -
每日一题 - 002 - 荷兰国旗问题(数组内容分三块)
2022-03-18 21:31:40每日一题系列 我是喜欢佳美宝贝,喜欢编程,喜欢动漫,喜欢健身的吴小哲同学 欢迎您阅读我的博客 您的评论点赞收藏是对我创作最大的鼓励和帮助~ 文章目录 荷兰国旗问题(c语言实现) 思路一:暴力求解法 代码一... -
荷兰国旗问题(顺序表和链表)
2020-04-09 18:50:06//荷兰国旗问题 顺序表 #include <iostream> using namespace std; typedef struct { int data[20]; int length; }SqList; void InitList(SqList* L) { L = (SqList*)malloc(sizeof(SqList)); ... -
荷兰国旗问题(颜色排序问题)
2018-12-21 21:44:31问题就成了荷兰国旗问题: ”荷兰国旗难题“问题描述 ”荷兰国旗难题“是计算机科学中的一个程序难题,它是由Edsger Dijkstra提出的。荷兰国旗是由红、白、蓝三色组成的。 现在有若干个红、白、蓝三种... -
【左神算法】荷兰国旗问题
2020-05-08 13:07:30荷兰国旗问题 给定一个数组arr,和一个数num,请把小于num的数放在数组的左边,等于num的数放在数组的中间, 大于num的数放在数组的右边。 2.code 思路: 荷兰国旗问题的解决 * 1.设定less 为-1 位置 more 为arr.... -
算法学习笔记3-荷兰国旗问题
2019-12-10 10:35:38荷兰国旗问题(partition问题) 题目是:要求重新排列一个由字符R,W,B(R代表红色,W代表白色,B代表蓝色,这都是荷兰国旗的颜色)构成的数组,使得所有的R都排在最前面,W排在其次,B排在最后。为荷兰国旗问题... -
顺序表解决荷兰国旗问题
2018-12-20 21:02:22- 顺序表解决荷兰国旗问题,设有一个条块序列,每个条块为红(0)、白(1)、兰(2)三种颜色的一种。假设该序列采用顺序表存储,设计一个时间复杂度为O(n)的算法,使得这些条块按红、白、兰的顺序排好。 ![...