C#을 사용하여 추가 공간 없이 배열(네덜란드 플래그)에서 0,1,2를 정렬하는 방법은 무엇입니까?

낮음, 중간, 높음의 3점슛이 필요합니다. 우리는 시작 부분에 낮은 포인터와 중간 포인터를 사용하고 높은 포인터는 주어진 배열의 끝을 가리킬 것입니다.

배열 [mid] =0인 경우 배열 [mid]를 배열 [low]]로 바꾸고 두 포인터를 한 번 증가시킵니다.

array[mid] = 1이면 스왑이 필요하지 않습니다. 중간 포인터를 한 번 증가시킵니다.

배열 [mid] = 2인 경우 배열 [mid]를 배열 [high]로 바꾸고 상위 포인터를 한 번 감소시킵니다.

시간 복잡도 - O(N)

예

실시간 데모

using System;
namespace ConsoleApplication{
   public class Arrays{
      private void Swap(int[] arr, int pos1, int pos2){
         int temp = arr[pos1];
         arr[pos1] = arr[pos2];
         arr[pos2] = temp;
      }
      public void DutchNationalFlag(int[] arr){
         int low = 0;
         int mid = 0;
         int high = arr.Length - 1;
         while (mid <= high){
            if (arr[mid] == 0){
               Swap(arr, low, mid);
               low++;
               mid++;
            }
            else if (arr[mid] == 2){
               Swap(arr, high, mid);
               high--;
            }
            else{
               mid++;
            }
         }
      }
}
class Program{
   static void Main(string[] args){
         Arrays a = new Arrays();
         int[] arr = { 2, 1, 1, 0, 1, 2, 1, 2, 0, 0, 1 };
         a.DutchNationalFlag(arr);
         for (int i = 0; i < arr.Length; i++){
            Console.WriteLine(arr[i]);
         }
         Console.ReadLine();
      }
   }
}

Output

0 0 0 0 1 1 1 1 2 2 2

위 내용은 C#을 사용하여 추가 공간 없이 배열(네덜란드 플래그)에서 0,1,2를 정렬하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!