java - 四种颜色的荷兰国旗算法

Question

我经历了两种和三种颜色的解决方案，但我无法获得四种颜色的解决方案。

请帮忙。

会rrbb????yyyggg吗？我们将如何交换绿旗？

我尝试了下面的解决方案，但无法将最后一个黄色换成绿色。

  public class count123 {

// Java program to sort an array of 0, 1 and 2,3

    static void sort0123(int a[], int arr_size)
    {
        int lo = 0;
        int hi = arr_size - 1;
        int mid = 0,temp=0;
        int h2=arr_size - 1;
        while (mid <= hi)
        {
            switch (a[mid])
            {
            case 0:
            {
                temp = a[lo];
                a[lo] = a[mid];
                a[mid] = temp;
                lo++;
                mid++;
                break;
            }
            case 1:
                mid++;
                break;
            case 2:
            {
                temp = a[mid];
                a[mid] = a[hi];
                a[hi] = temp;

                hi--;
                h2=hi;
                break;
            }
            case 3:{
                temp = a[mid];
                a[mid] = a[h2];
                a[h2] = temp;
            //  h2--;
                //hi=h2;
                break;

            }
            }
        }
    }

    /* Utility function to print array arr[] */
    static void printArray(int arr[], int arr_size)
    {
        int i;
        for (i = 0; i < arr_size; i++)
            System.out.print(arr[i]+" ");
            System.out.println("");
    }

    /*Driver function to check for above functions*/
    public static void main (String[] args)
    {
        int arr[] = {0, 1, 0,1,2,2,0,3,3,0,0,1};
        int arr_size = arr.length;
        sort0123(arr, arr_size);
        System.out.println("Array after seggregation ");
        printArray(arr, arr_size);
    }
}
/*This code is contributed by Devesh Agrawal*/

Answer 1

我运行您的代码并意识到您的代码进入了无限循环，这让您的程序什么也不做。

在 main 方法中，sort0123(arr, arr_size);被调用并且在这个方法中 while (mid <= hi)，mid = 6 和 hi = 9 并且这意味着6 <= 9并且由于这个原因，这个条件无限地返回真，因为它总是在某个点进入案例 3 并且在情况 3 中，mid 和 hi 的值没有改变。

为了能够运行您的代码，您应该更改mid和/或hi逻辑上的值，并且使用它，您的程序可以按照您想要的方式运行。

Answer 2

我在ideone中的解决方案

#include <iostream>
using namespace std;



void DutchNationalFlag4(int * arr , int n )
{
    int low = 0 , mid1 = 0 , mid2 = n- 1 , high = n-1 ;
    int temp;
 
    // This type of problems are best solved by using invariants 
 
    // arr[ 0 .. low -1 ] conatins 0
    // arr[ low .. mid1 -1 ] contains 1
    // arr[ mid1 .. mid2 ] is unknown
    // arr[ mid2 + 1 ... high - 1 ] contains 2
    // arr[ high .. n-1 ] contains 3
 
    // termination condition : Evert Iteration unkown length decreases so eventually will be Zero
    while( mid1 <= mid2 )
    {
        switch( arr[ mid1 ])
        {
            case 0 :
            {
                std::swap( arr[ low ] , arr [ mid1 ] );
                low ++ ;
                mid1 ++;
                break;
            }
 
            case 1 :
            {
                mid1 ++;
                break;
            }
 
            case 2 :
            {
                std::swap( arr[ mid1 ] , arr[ mid2 ]);
                mid2 -- ;
                break;
            }
 
            case 3 :
            {
                std::swap( arr[ mid1 ] , arr[ mid2 ]);
                std::swap( arr[ mid2 ] , arr[ high ]);
                mid2 --;
                high --;
                break;
            }
 
        }
    }
 
    for( int i =0 ; i < n ; i++)
    {
        cout << arr[ i ] << " " ;
    }
}
 
int main() 
{
    int arr[] = {1,2,3,0,2,1,3,0,2,1,0,1,3,1,0,2,1,0};
    int n = sizeof(arr) / sizeof(arr[0]) ;
    DutchNationalFlag4(arr , n );
    return 0;
}

我已经在上面的链接中解决了！干杯

当您提出问题时，请尽量说得更清楚。还要确保您的变量是直观命名的，或者您提供了适当的注释。坦率地说，我对 hi 和 h2 ， mid 感到困惑！

Answer 3

关于荷兰国旗聚合的要点是始终保持不变量。处于 0000...11..XXX..222 等状态

1. lo 将始终位于第一个“1”（如果存在）
2. mid 永远是第一个未知数
3. 嗨总是在最后一个未知数

对于 4 种颜色变化，假设您按 0、1、3、2 的顺序排序，就像代码中的情况一样，则需要按如下方式调整规则：

3. 嗨总是在最后 3
4. h2 总是在最后一个未知数

按照上述规则，代码将需要通过以下方式进行更改：

while (mid <= h2)

. . .

case 2:
        {
            temp = a[mid];
            a[mid] = a[hi];
            a[hi] = temp;

            hi--;
            h2--;
            break;
        }
case 3:{
            temp = a[mid];
            a[mid] = a[h2];
            a[h2] = temp;
            h2--;
            break;

        }

要按 0、1、2、3 的顺序排序，只需交换“2”和“3”的 case 语句。

PS：请使问题具有描述性，以帮助人们轻松理解问题。

Answer 4

这是我用python编写的解决方案。它背后的基本原理是在中间的左右子阵列之间挤压第四种颜色（中间右侧颜色）。它随着算法的进行定义颜色。

它具有 O(n) 时间复杂度和 O(1) 空间复杂度

from typing import List

def dutch_variant_four_colors(array: List[int]) -> List[int]:
    left = array[0]
    mid_left = None
    right = None

    left_i = 0
    mid_left_i = 0
    mid_right_i = len(array)
    right_i = len(array)

    while mid_left_i < right_i and mid_left_i < mid_right_i:
        if (array[mid_left_i] == left):
            array[mid_left_i], array[left_i] = array[left_i], array[mid_left_i]
            mid_left_i += 1
            left_i += 1
        elif (right is None or array[mid_left_i] == right):
            right_i -= 1
            mid_right_i = right_i
            array[mid_left_i], array[right_i] = array[right_i], array[mid_left_i]
            right = array[right_i]
        else:  # it is a mid value
            if (mid_left is None):
                mid_left = array[mid_left_i]
            if (array[mid_left_i] == mid_left):
                mid_left_i += 1
            else:
                mid_right_i -= 1
                array[mid_left_i], array[mid_right_i] = array[mid_right_i], array[mid_left_i]

    return array


# Sample usages
print(dutch_variant_four_colors([1,1,3,3,4,3,2,2]))
print(dutch_variant_four_colors([1,2,3,4,2,3,1,3]))
print(dutch_variant_four_colors([1,2,3,4,4]))
print(dutch_variant_four_colors([0,1,2,5,5,2,2,0]))
print(dutch_variant_four_colors([1,0,3,0,5,5]))
print(dutch_variant_four_colors([1,2,3,2,5,1,1,3]))
print(dutch_variant_four_colors([5,1,2,3,2,1,1,3]))
print(dutch_variant_four_colors([3,2,5,1]))
print(dutch_variant_four_colors([3,2,1,5]))
print(dutch_variant_four_colors([3,2,1,3,5,2,2,1,2,3,5,3,2,1,3,5,3,3,2,2,2,5,5,5,3,3,2,5,3,1,2,3,2,1,3,2,1,1,2,3,2,3,2,1,2,3,2,1,2,3,2,2,2,2,2,3,3,3,1,2,2,1,1,2,3]))

要点可在https://gist.github.com/lopespm/81a336871ce6074f63f3cad349c3a95d

Answer 5

let a:string[] = ['1','2','1','0','2','4','3','0','1','3'];
    function sort3(a:string[]):void{
        let low = 0;
        let mid1 = 0;
        let mid2 = 0;
        let mid3 = 0;
        let high = a.length - 1;
        while(mid3<=high){
            switch(a[mid3]){
                case '0': [a[mid3],a[low]] = [a[low],a[mid3]];
                        low++;
                        if(mid1 < low)
                        mid1++;
                        if(mid2 < mid1)
                        mid2++;
                        if(mid3 < mid2)
                        mid3++;
                        break;

                case '1': [a[mid3],a[mid1]] = [a[mid1],a[mid3]];
                        mid1++;
                        if(mid2 < mid1)
                        mid2++;
                        if(mid3 < mid2)
                        mid3++
                        break;

                case '2': [a[mid2],a[mid3]] = [a[mid3],a[mid2]];
                            mid2++;
                            mid3++;
                       break;

                case '3':
                        mid3++;break;

                case '4': [a[mid3],a[high]] = [a[high],a[mid3]];
                            high--;
            }
        }
    }

Answer 6

//Dutch National Flag for N different values Optimized 
//O(n) optimized solution.
//O(1) space needed where x is distinct colors (it will not change as no. of values increases)

public static void DutchNationalFlagforNvaluesOptimized(int distinctFlags, int[] flags)
        {
            int high = distinctFlags - 1, mid = distinctFlags - 2;

            int[] indexArr = new int[distinctFlags];
            for (int i = 0; i < high; i++)
            {
                indexArr[i] = 0;
            }
            indexArr[high] = flags.Length - 1;// index Array is distinct flags indexes


            for (; indexArr[mid] <= indexArr[high]; )
            {
                if (flags[indexArr[mid]] == high)
                {
                    int temp = flags[indexArr[high]];
                    flags[indexArr[high]] = flags[indexArr[mid]];
                    flags[indexArr[mid]] = temp;

                    indexArr[high]--;
                }
                else
                    if (flags[indexArr[mid]] == mid)
                    {
                        indexArr[mid]++;
                    }
                    else
                    {
                        int currentMidValue = flags[indexArr[mid]];

                        for (int i = mid; i > currentMidValue; i--)
                        {
                            int temp = flags[indexArr[i]];
                            flags[indexArr[i]] = flags[indexArr[i - 1]];
                            flags[indexArr[i - 1]] = temp;
                            indexArr[i]++;
                        }
                        indexArr[currentMidValue]++;
                    }
            }
            for (int i = 0; i < flags.Length; i++)
            {
                System.Console.Write(flags[i] + ", ");
            }
        }