Java를 사용하여 0, 1, 2의 배열 정렬-java지도 시간-php.cn

Java를 사용하여 0, 1, 2의 배열 정렬

王林

풀어 주다： 2023-09-09 19:57:09

앞으로

1183명이 탐색했습니다.

Java를 사용하여 0, 1, 2의 배열 정렬

0, 1, 2로 구성된 배열이 주어지면 모든 0이 1보다 앞에 오고 모든 2가 맨 마지막에 오도록 요소를 정렬하세요. 배열의 모든 요소를 제자리에서 정렬해야 합니다.

DNF(Dutch Flag) 정렬 알고리즘을 사용하여 이 문제를 해결할 수 있습니다. 예를 들어,

Input-1 -

arr[ ]= {2,0,0,1,2,1 }

로그인 후 복사

Output -

0 0 1 1 2 2

로그인 후 복사

Explanation − DNF 정렬 알고리즘을 사용하여 0, 1, 2가 포함된 배열을 정렬하면 {0, 0, 1,1,2,2}.

Input-2 −

arr[ ] = {0,1,1,2,1,1,0}

로그인 후 복사

Output -

0 0 1 1 1 1 2

로그인 후 복사

Explanation − DNF 정렬 알고리즘을 사용하여 0, 1, 2를 포함하는 주어진 요소 배열을 정렬하면 {0,0,1, 1,1,1,2}.

이 문제를 해결하는 방법

주어진 0, 1, 2 배열에서 DNF 정렬 알고리즘을 사용할 수 있습니다.

DNF 정렬 알고리즘 − 이 알고리즘에는 전체 배열을 순회하고 필요한 요소를 교환하기 위해 3개의 포인터가 필요합니다.

배열의 시작 부분에 낮은 포인터를 만들고 배열의 끝을 가리키는 높은 포인터를 만듭니다.
배열의 중간점을 찾아 배열의 처음부터 끝까지 반복하는 중간점을 만듭니다.
배열의 중간 포인터가 '0'이면 낮은 포인터를 가리키는 요소를 바꿉니다. 낮은 및 중간 포인터를 추가했습니다.
배열의 중간 포인터가 '2'인 경우 높은 포인터를 가리키는 요소로 바꿉니다. 중간 포인터를 늘리고 높은 포인터를 줄입니다.
배열의 중간 포인터가 '1'이면 중간 포인터를 증가시킵니다.

Example

Demonstration

public class Solution {
   public static void binarySorting(int arr[], int n){
      int low=0;
      int high= n-1;
      int mid=0;
      while(mid<=high){
         if(arr[mid]==0){
            int temp= arr[mid];
            arr[mid]= arr[low];
            arr[low]= temp;
            mid++;
            low++;
         }
         if(arr[mid]==1){
            mid++;
         }
         if(arr[mid]==2){
            int temp= arr[mid];
            arr[mid]= arr[high];
            arr[high]= temp;
            high--;
         }
      }
   }
   public static void print(int arr[], int n){
      for (int i = 0; i < n; i++)
         System.out.print(arr[i] +" ");
   }
   public static void main(String[] args){
      int arr[] ={ 0,0,1,0,1,0,1,2,2};
      int n = arr.length;
      binarySorting(arr, n);
      print(arr, n);
   }
}

로그인 후 복사