当前位置:网站首页>Rainbow sorting | Dutch flag problem
Rainbow sorting | Dutch flag problem
2020-11-09 12:28:00 【Yard farmland】
WeChat search 「 Yard farmland, Xiao Qi 」, Focus on this program in New York , reply 「01-05」 You can get a selection of computer books 、 Personal writing notes 、 Big factory surface 、 Interview materials and other resources , mua ~
The Dutch flag problem is also called tricolor order , Or rainbow sort ,
Because the Dutch flag has three colors , The problem with this question is to give you three colors , Arrange in the given order .
Yes, of course , There are various ways to ask questions , Some give numbers , Some give letters , But the essence is the same .
For example, give you an array of three numbers :312312312231111122113,
The requirements are as follows 1 2 3 Put it in order , namely : 111111111222222222223333333333
( Please don't really count , You lose when you get serious )
Or use our classic 「 Baffle method 」.
In the express line , We used two baffles to divide the array into three areas :
<= pivot; Unordered range ;> pivot
So here's three baffles , Divided into four areas :
1, 2, 3, Unordered range
Partition
say concretely , use i, j, k These three hands are divided :
[0, i): save 1
[i, j): save 2
(k, array.length-1]: save 3
here j Put it to the left and right of unsorted intervals , But basically we put it on the left , So we don't have to “ new in order to be different ”.
initialization :
i = 0;
j = 0;
k = array.length - 1;
In this way, we can guarantee 1,2,3 Each interval of is empty .
We go through Watch the pointer j Pointing elements To keep narrowing the unsorted range , Until it's empty .
Example :1232312
To look good , The ordered elements we use RGB Three primary colors to mark .
Step1.
The pointer j Point to 1, and 1 Should be placed in [0, i) Within the interval , The pointer should be put here i And a pointer j Exchange the elements , And the two hands go forward .
Although at this point it doesn't make any difference whether it's a swap or not , But if i and j There are elements in between , There's a difference , such as Step7.
Step2.
The pointer j Point to 2, and 2 Should be placed in [i, j) Within the interval , therefore j++.
Step3.
The pointer j Point to 3, and 3 Should be placed in
(k, array.length-1] Within the interval , So here
j and k Point to the element exchange , also k--.
Notice that you can't j-- 了 , Because I haven't seen the new elements yet , I don't know what it is .
Step4.
The pointer j Point to 2, Same as Step2, Move the pointer directly j that will do .
Step5.
Keep moving the pointer j.
Step6.
Same as Step3.
Step7.
This step is obvious ,
because 1 Should be placed in [0,i) Section , So here's the pointer i,j Exchange the elements you point to , also i++, j++.
So the unsorted interval is empty , We're in line ~
Time complexity
This algorithm bottle neck That's it while loop In the , Every cycle is O(1), The total is O(n).
Spatial complexity
O(1)
If you like this article , Remember to leave me a like message ~ Your support and recognition , It's the biggest driving force of my creation , See you in the next article !
This is Qi , New York program , Lifelong learners , Every night 9 spot , Let's meet you in the cloud study room !
See my... For more dry articles Github: https://github.com/xiaoqi6666/NYCSDE
版权声明
本文为[Yard farmland]所创,转载请带上原文链接,感谢
边栏推荐
- 服务应用 ClockService安卓实现闹钟
- 移动安全加固助力 App 实现全面、有效的安全防护
- Depth analysis based on synchronized lock
- Large scale project Objective-C - nsurlsession access SMS verification code application example sharing
- JVM learning (5) - execution subsystem
- New features of Fedora 33 workstation
- 10款必装软件,让Windows使用效率飞起!
- Ali, Tencent, Baidu, Netease, meituan Android interview experience sharing, got Baidu, Tencent offer
- Oh, my God! Printing log only knows log4j?
- Android Development - service application, timer implementation (thread + service)
猜你喜欢
iPhone“连到系统上的设备没有发挥作用”原因分析及解决方法 20200105
Nine kinds of distributed primary key ID generation schemes of sub database and sub table are quite comprehensive
Interview summary on November 7, 2020 (interview 12K)
JVM learning (5) - execution subsystem
Nine kinds of distributed primary key ID generation schemes of sub database and sub table are quite comprehensive
SQL Chapter 2 Chapter 3
Recommended tools for Mac
android studio AIDL的使用
技美那么贵,不如找顾问 | AALab企业顾问业务
In the future, China Telecom will make cloud computing service the main business of China Telecom
随机推荐
Reread reconstruction
Tutorial system unity online course double 11 preferential registration is in progress
彩虹排序 | 荷兰旗问题
Android rights
20201107第16课,使用Apache服务部署静态网站;使用Vsftpd服务传输文件
Android 集成支付的四部曲
Nine kinds of distributed primary key ID generation schemes of sub database and sub table are quite comprehensive
EFF 认为 RIAA 正在“滥用 DMCA”来关闭 YouTube-DL
利用 Python 一键下载网易云音乐 10W+ 乐库
Wechat circle
inet_pton()和inet_ntop()函数详解
Clock service Android implementation of alarm clock
TiDB x 微众银行 | 耗时降低 58%,分布式架构助力实现普惠金融
inet_ Pton () and INET_ Detailed explanation of ntop() function
Kubernetes业务日志收集与监控
Learning notes of nodejs
How to ensure that messages are not consumed repeatedly? (how to ensure the idempotent of message consumption)
手写Koa.js源码
Wealth and freedom? Ant financial services suspended listing, valuation or decline after regulation
AndroidStudio导入定制化的framework classess.jar AS 4.0.1版本亲测有效