Cousera Algorithms
PartI Question and answer after class in the second week , There is such a problem , There was no idea , Until the third week of merging , To figure out what to do , Here, record your ideas and the final code .

Problem description


In short , The problem is that there are red, white and blue balls n Random arrangement , And that's what we're going to do n Press the ball red , white , In blue order . That's why it's called the Dutch flag , The picture below shows the Dutch flag , It can be described as vivid .



The biggest problem with this problem is that it only allows one iteration to arrange the array , If there is no such requirement , The problem is very simple , Just one ball, one ball test .

terms of settlement


Inspired by merging and sorting , I think I want to solve this problem , We need to 3 Pointers ,lo,hi,current, Respectively represent the starting point and dividing point of the white ball , Termination cut off point , Current position point . This is the way to answer the question : First create a length of n Array of ,lo,current In array 0 position ,hi In array n-1 position . If the current position, we check that the color is red , and lo=current, Then the lo,current Duga 1. If the current color is red , and lo<current That means , In front of the current red ball, there has been a white ball , To get the red ball to the front , We need another lo Position of the ball and current Position of the ball exchange position , At the same time lo,current All forward 1 position . If the current White ball , that lo Keep still ,current plus 1. If you meet a basketball ball, then , We'll first move it to the back of the array , We should exchange current and hi Elements of position , meanwhile current Keep still ( Because of the current current The position of the ball has not been checked , It was before hi The ball of position ),hi To move one bit backward , soon hi-1. In this way, the array can be arranged according to the rules .

Sort it out :

                red =1

                white =0

                blue =2

                if (color(current)==1 && less(lo,current) )

                   swap(lo,current); // Swap positions

                    lo++;

                    current++;

                else if (color(currrent)==1 && color(lo)==1)

                   lo++;

                   current++;

                else if(color(current)==0)

                   current++;

                else if (color(current)==2)

                   swap(current,hi);

                   hi--;

It will be clearer if you just take a sketch paper and draw it



code
import java.util.Arrays; import edu.princeton.cs.algs4.StdRandom; public class
DutchNationalFlag { /* The Dutch flag issue , There are red, white and blue balls arranged randomly in the array , Our aim is to *
Arrange the three balls in red, white and blue order , And it requires traversing the array only once */ public static final int red = 0; public static
final int white = 1; public static final int blue = 2; private int n; private
int[] buckets; public DutchNationalFlag (int[] buckets) { // Create an array n =
buckets.length; this.buckets = buckets; } public void sort() { int lo = 0; //
The starting point of the white sphere int hi = n-1; // The termination point of the white sphere int current = lo; // Current pointer while (current <=
hi) { switch(color(current)) { case red: if (current != lo) swap (current ,
lo); current ++; lo ++; break; case white: current ++; break; case blue: swap
(current , hi); hi--; break; } } } private void swap(int a, int b) { //
Swapping elements in two places int temp = buckets[b]; buckets[b] = buckets[a]; buckets[a] = temp; }
private int color(int c) { // Detects the color of the current location return buckets[c]; } public static void
main(String[] args) { int n = 10; int [] buckets = new int[n]; for (int i = 0;
i < n; i++) { buckets[i] = StdRandom.uniform(3); } DutchNationalFlag s = new
DutchNationalFlag (buckets); System.out .println(Arrays.toString(buckets));
s.sort(); System.out .println(Arrays.toString(buckets)); } }
The code I wrote for this course will be uploaded to me in the future github upper :https://github.com/zhengmingzhang
<https://github.com/zhengmingzhang>