给定一个数组 A[] 由0、1和2组成。任务是编写一个对给定数组排序的函数。函数应该将所有0放在第一位，然后将所有1和所有2放在最后。 例如：
null
Input: {0, 1, 2, 0, 1, 2}Output: {0, 0, 1, 1, 2, 2}Input: {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1}Output: {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}
本文讨论了一个简单的解决方案( 对0、1和2的数组进行排序（简单计数） )发帖。 方法1
- 方法： 这个问题与我们以前的帖子类似 在数组中分隔0和1 这两个问题都是著名的 荷兰国旗问题 . 这个问题是由三种颜色构成的，这里的“0”、“1”和“2”。该阵列分为四个部分：
- a[1..Lo-1]零（红色）
- a[Lo..Mid-1]个（白色）
- 一个[中..嗨]未知
- a[Hi+1..N]two（蓝色）
- 如果第i个元素为0，则将该元素切换到低范围，从而缩小未知范围。
- 同样，如果元素为1，则保持原样，但缩小未知范围。
- 如果元素为2，则将其与高范围的元素交换。
- 算法：
- 保持三个指数低=1、中=1和高=N，有四个范围，1到低（范围包含0）、低到中（范围包含1）、中到高（范围包含未知元素）和高到N（范围包含2）。
- 从开始到结束遍历阵列，中间小于高。（循环计数器为i）
- 如果元素为0，则将该元素与索引低的元素交换，并更新low=low+1和mid=mid+1
- 如果元素为1，则更新mid=mid+1
- 如果元素为2，则将元素与索引高的元素交换，并更新高=高–1和更新i=i–1。因为交换的元素没有被处理
- 打印数组。
- 排练： 在整个过程的一部分，一些红色、白色和蓝色元素是已知的，并且位于“正确”的位置。通过检查[Mid]：
检查一个[中间]。有三种可能性： [Mid]是（0）红色、（1）白色或（2）蓝色。 案例（0）a[Mid]为红色，交换a[Lo]和a[Mid]；Lo++；中段++
案例（1）a[Mid]为白色，Mid++
案例（2）a[Mid]为蓝色，交换a[Mid]和a[Hi]；嗨——
继续到Mid>Hi。
- 实施：
C++
// C++ program to sort an array // with 0, 1 and 2 in a single pass #include <bits/stdc++.h> using namespace std; // Function to sort the input array, // the array is assumed // to have values in {0, 1, 2} void sort012( int a[], int arr_size) { int lo = 0; int hi = arr_size - 1; int mid = 0; // Iterate till all the elements // are sorted while (mid <= hi) { switch (a[mid]) { // If the element is 0 case 0: swap(a[lo++], a[mid++]); break ; // If the element is 1 . case 1: mid++; break ; // If the element is 2 case 2: swap(a[mid], a[hi--]); break ; } } } // Function to print array arr[] void printArray( int arr[], int arr_size) { // Iterate and print every element for ( int i = 0; i < arr_size; i++) cout << arr[i] << " " ; } // Driver Code int main() { int arr[] = { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 }; int n = sizeof (arr) / sizeof (arr[0]); sort012(arr, n); cout << "array after segregation " ; printArray(arr, n); return 0; } // This code is contributed by Shivi_Aggarwal |
C
// C program to sort an array with 0, 1 and 2 // in a single pass #include <stdio.h> /* Function to swap *a and *b */ void swap( int * a, int * b); // Sort the input array, the array is assumed to // have values in {0, 1, 2} void sort012( int a[], int arr_size) { int lo = 0; int hi = arr_size - 1; int mid = 0; while (mid <= hi) { switch (a[mid]) { case 0: swap(&a[lo++], &a[mid++]); break ; case 1: mid++; break ; case 2: swap(&a[mid], &a[hi--]); break ; } } } /* UTILITY FUNCTIONS */ void swap( int * a, int * b) { int temp = *a; *a = *b; *b = temp; } /* Utility function to print array arr[] */ void printArray( int arr[], int arr_size) { int i; for (i = 0; i < arr_size; i++) printf ( "%d " , arr[i]); printf ( "n" ); } /* driver program to test */ int main() { int arr[] = { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 }; int arr_size = sizeof (arr) / sizeof (arr[0]); int i; sort012(arr, arr_size); printf ( "array after segregation " ); printArray(arr, arr_size); getchar (); return 0; } |
JAVA
// Java program to sort an array of 0, 1 and 2 import java.io.*; class countzot { // Sort the input array, the array is assumed to // have values in {0, 1, 2} static void sort012( int a[], int arr_size) { int lo = 0 ; int hi = arr_size - 1 ; int mid = 0 , temp = 0 ; 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--; 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 , 1 , 0 , 1 , 2 , 1 , 2 , 0 , 0 , 0 , 1 }; int arr_size = arr.length; sort012(arr, arr_size); System.out.println( "Array after seggregation " ); printArray(arr, arr_size); } } /*This code is contributed by Devesh Agrawal*/ |
Python3
# Python program to sort an array with # 0, 1 and 2 in a single pass # Function to sort array def sort012( a, arr_size): lo = 0 hi = arr_size - 1 mid = 0 while mid < = hi: if a[mid] = = 0 : a[lo], a[mid] = a[mid], a[lo] lo = lo + 1 mid = mid + 1 elif a[mid] = = 1 : mid = mid + 1 else : a[mid], a[hi] = a[hi], a[mid] hi = hi - 1 return a # Function to print array def printArray( a): for k in a: print (k,end = ' ' ) # Driver Program arr = [ 0 , 1 , 1 , 0 , 1 , 2 , 1 , 2 , 0 , 0 , 0 , 1 ] arr_size = len (arr) arr = sort012( arr, arr_size) print ( "Array after segregation :" ,) printArray(arr) # Contributed by Harshit Agrawal |
C#
// C# program to sort an // array of 0, 1 and 2 using System; class GFG { // Sort the input array, the array is assumed to // have values in {0, 1, 2} static void sort012( int [] a, int arr_size) { int lo = 0; int hi = arr_size - 1; int mid = 0, temp = 0; 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--; break ; } } } } /* Utility function to print array arr[] */ static void printArray( int [] arr, int arr_size) { int i; for (i = 0; i < arr_size; i++) Console.Write(arr[i] + " " ); Console.WriteLine( "" ); } /*Driver function to check for above functions*/ public static void Main() { int [] arr = { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 }; int arr_size = arr.Length; sort012(arr, arr_size); Console.Write( "Array after seggregation " ); printArray(arr, arr_size); } } // This code is contributed by Sam007 |
PHP
<?php // PHP program to sort an array // with 0, 1 and 2 in a single pass // Sort the input array, the array is // assumed to have values in {0, 1, 2} function sort012(& $a , $arr_size ) { $lo = 0; $hi = $arr_size - 1; $mid = 0; while ( $mid <= $hi ) { switch ( $a [ $mid ]) { case 0: swap( $a [ $lo ++], $a [ $mid ++]); break ; case 1: $mid ++; break ; case 2: swap( $a [ $mid ], $a [ $hi --]); break ; } } } /* UTILITY FUNCTIONS */ function swap(& $a , & $b ) { $temp = $a ; $a = $b ; $b = $temp ; } /* Utility function to print array arr[] */ function printArray(& $arr , $arr_size ) { for ( $i = 0; $i < $arr_size ; $i ++) echo $arr [ $i ]. " " ; echo "" ; } // Driver Code $arr = array (0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1); $arr_size = sizeof( $arr ); sort012( $arr , $arr_size ); echo "array after segregation " ; printArray( $arr , $arr_size ); // This code is contributed // by ChitraNayal ?> |
Javascript
<script> // Javascript program to sort an array of 0, 1 and 2 // Sort the input array, the array is assumed to // have values in {0, 1, 2} function sort012(a,arr_size) { let lo = 0; let hi = arr_size - 1; let mid = 0; let temp = 0; while (mid <= hi) { if (a[mid] == 0) { temp = a[lo]; a[lo] = a[mid]; a[mid] = temp; lo++; mid++; } else if (a[mid] == 1) { mid++; } else { temp = a[mid]; a[mid] = a[hi]; a[hi] = temp; hi--; } } } /* Utility function to print array arr[] */ function printArray(arr,arr_size) { let i; for (i = 0; i < arr_size; i++) { document.write(arr[i] + " " ); } document.write( "<br>" ); } /*Driver function to check for above functions*/ let arr= [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 ]; let arr_size = arr.length; sort012(arr, arr_size); document.write( "Array after seggregation <br>" ) printArray(arr, arr_size); // This code is contributed by rag2127 </script> |
- 输出：
array after segregation 0 0 0 0 0 1 1 1 1 1 2 2
- 复杂性分析：
- 时间复杂性： O（n）。 只需要遍历数组一次。
- 空间复杂性： O（1）。 不需要额外的空间。
- 方法：
计算给定数组中0、1和2的数量。然后在开始时存储所有0，然后存储所有1，然后存储所有2。
- 算法：
- 保持三个计数器c0计数0，c1计数1，c2计数2
- 遍历数组，如果元素为0，则增加c0的计数；如果元素为1，则增加c1的计数；如果元素为2，则增加c2的计数
- 现在再次遍历数组，用0替换第一个c0元素，用1替换下一个c1元素，用2替换下一个c2元素。
- 实施：
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Utility function to print the contents of an array void printArr( int arr[], int n) { for ( int i = 0; i < n; i++) cout << arr[i] << " " ; } // Function to sort the array of 0s, 1s and 2s void sortArr( int arr[], int n) { int i, cnt0 = 0, cnt1 = 0, cnt2 = 0; // Count the number of 0s, 1s and 2s in the array for (i = 0; i < n; i++) { switch (arr[i]) { case 0: cnt0++; break ; case 1: cnt1++; break ; case 2: cnt2++; break ; } } // Update the array i = 0; // Store all the 0s in the beginning while (cnt0 > 0) { arr[i++] = 0; cnt0--; } // Then all the 1s while (cnt1 > 0) { arr[i++] = 1; cnt1--; } // Finally all the 2s while (cnt2 > 0) { arr[i++] = 2; cnt2--; } // Print the sorted array printArr(arr, n); } // Driver code int main() { int arr[] = { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 }; int n = sizeof (arr) / sizeof ( int ); sortArr(arr, n); return 0; } |
JAVA
// Java implementation of the approach import java.io.*; class GFG { // Utility function to print the contents of an array static void printArr( int arr[], int n) { for ( int i = 0 ; i < n; i++) System.out.print(arr[i] + " " ); } // Function to sort the array of 0s, 1s and 2s static void sortArr( int arr[], int n) { int i, cnt0 = 0 , cnt1 = 0 , cnt2 = 0 ; // Count the number of 0s, 1s and 2s in the array for (i = 0 ; i < n; i++) { switch (arr[i]) { case 0 : cnt0++; break ; case 1 : cnt1++; break ; case 2 : cnt2++; break ; } } // Update the array i = 0 ; // Store all the 0s in the beginning while (cnt0 > 0 ) { arr[i++] = 0 ; cnt0--; } // Then all the 1s while (cnt1 > 0 ) { arr[i++] = 1 ; cnt1--; } // Finally all the 2s while (cnt2 > 0 ) { arr[i++] = 2 ; cnt2--; } // Print the sorted array printArr(arr, n); } // Driver code public static void main(String[] args) { int arr[] = { 0 , 1 , 1 , 0 , 1 , 2 , 1 , 2 , 0 , 0 , 0 , 1 }; int n = arr.length; sortArr(arr, n); } } // This code is contributed by shubhamsingh10 |
Python3
# Python implementation of the approach # Utility function to print contents of an array def printArr(arr, n): for i in range (n): print (arr[i],end = " " ) # Function to sort the array of 0s, 1s and 2s def sortArr(arr, n): cnt0 = 0 cnt1 = 0 cnt2 = 0 # Count the number of 0s, 1s and 2s in the array for i in range (n): if arr[i] = = 0 : cnt0 + = 1 elif arr[i] = = 1 : cnt1 + = 1 elif arr[i] = = 2 : cnt2 + = 1 # Update the array i = 0 # Store all the 0s in the beginning while (cnt0 > 0 ): arr[i] = 0 i + = 1 cnt0 - = 1 # Then all the 1s while (cnt1 > 0 ): arr[i] = 1 i + = 1 cnt1 - = 1 # Finally all the 2s while (cnt2 > 0 ): arr[i] = 2 i + = 1 cnt2 - = 1 # Print the sorted array printArr(arr, n) # Driver code arr = [ 0 , 1 , 1 , 0 , 1 , 2 , 1 , 2 , 0 , 0 , 0 , 1 ] n = len (arr) sortArr(arr, n) #This code is contributed by shubhamsingh10 |
C#
// C# implementation of the approach using System; class GFG { // Utility function to print the contents of an array static void printArr( int [] arr, int n) { for ( int i = 0; i < n; i++) Console.Write(arr[i] + " " ); } // Function to sort the array of 0s, 1s and 2s static void sortArr( int [] arr, int n) { int i, cnt0 = 0, cnt1 = 0, cnt2 = 0; // Count the number of 0s, 1s and 2s in the array for (i = 0; i < n; i++) { switch (arr[i]) { case 0: cnt0++; break ; case 1: cnt1++; break ; case 2: cnt2++; break ; } } // Update the array i = 0; // Store all the 0s in the beginning while (cnt0 > 0) { arr[i++] = 0; cnt0--; } // Then all the 1s while (cnt1 > 0) { arr[i++] = 1; cnt1--; } // Finally all the 2s while (cnt2 > 0) { arr[i++] = 2; cnt2--; } // Print the sorted array printArr(arr, n); } // Driver code public static void Main() { int [] arr = { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 }; int n = arr.Length; sortArr(arr, n); } } // This code is contributed by shubhamsingh10 |
Javascript
<script> // javascript implementation of the approach // Utility function to print the contents of an array function printArr( arr, n) { for (let i = 0; i < n; i++) document.write(arr[i] + " " ); } // Function to sort the array of 0s, 1s and 2s function sortArr( arr, n) { let i, cnt0 = 0, cnt1 = 0, cnt2 = 0; // Count the number of 0s, 1s and 2s in the array for (i = 0; i < n; i++) { switch (arr[i]) { case 0: cnt0++; break ; case 1: cnt1++; break ; case 2: cnt2++; break ; } } // Update the array i = 0; // Store all the 0s in the beginning while (cnt0 > 0) { arr[i++] = 0; cnt0--; } // Then all the 1s while (cnt1 > 0) { arr[i++] = 1; cnt1--; } // Finally all the 2s while (cnt2 > 0) { arr[i++] = 2; cnt2--; } // Print the sorted array printArr(arr, n); } // Driver program to test above function let arr = [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]; let n = arr.length; // Function calling sortArr(arr, n); // This code is contributed by jana_sayantan. </script> |
输出：
0 0 0 0 0 1 1 1 1 1 2 2
- 复杂性分析：
- 时间复杂性： O（n）。 只需要对数组进行两次遍历。
- 空间复杂性： O（1）。 因为不需要额外的空间。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
