Переместите все нули в начало и единицы в конец в массив случайных целых чисел
Для массива arr [] случайных целых чисел задача состоит в том, чтобы протолкнуть все нули в массиве в начало, а все единицы в конец массива. Обратите внимание, что порядок всех остальных элементов должен быть таким же.
Пример:
Input: arr[] = {1, 2, 0, 4, 3, 0, 5, 0}
Output: 0 0 0 2 4 3 5 1
Input: arr[] = {1, 2, 0, 0, 0, 3, 6};
Output: 0 0 0 2 3 6 1
Approach: Traverse the array from left to right and move all the elements which are not equal to 1 at the beginning and then put 1’s in the rest of the indices at the end of the array. Now, find the index of the last element which is not equal to 1 say lastInd and then starting from this index to the beginning of the array push all the elements which are not equal to 0 in the end till lastInd and then put 0’s in the beginning.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> using namespace std; // Utility function to print // the contenets of an array void printArr( int arr[], int n) { for ( int i = 0; i < n; i++) cout << arr[i] << " " ; } // Function that pushes all the zeros // to the start and ones to the end of an array void pushBinaryToBorder( int arr[], int n) { // To store the count of elements // which are not equal to 1 int count1 = 0; // Traverse the array and calculate // count of elements which are not 1 for ( int i = 0; i < n; i++) if (arr[i] != 1) arr[count1++] = arr[i]; // Now all non-ones elements have been shifted to // front and "count1" is set as index of first 1. // Make all elements 1 from count to end. while (count1 < n) arr[count1++] = 1; // Initialize lastNonBinary position to zero int lastNonOne = 0; // Traverse the array and pull non-zero // elements to the required indices for ( int i = n - 1; i >= 0; i--) { // Ignore the 1"s if (arr[i] == 1) continue ; if (!lastNonOne) { // Mark the position Of // last NonBinary integer lastNonOne = i; } // Place non-zero element to // their required indices if (arr[i] != 0) arr[lastNonOne--] = arr[i]; } // Put zeros to start of array while (lastNonOne >= 0) arr[lastNonOne--] = 0; } // Driver code int main() { int arr[] = { 1, 2, 0, 0, 0, 3, 6 }; int n = sizeof (arr) / sizeof (arr[0]); pushBinaryToBorder(arr, n); printArr(arr, n); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { // Utility function to print // the contenets of an array static void printArr( int arr[], int n) { for ( int i = 0 ; i < n; i++) System.out.print(arr[i]+ " " ); } // Function that pushes all the zeros // to the start and ones to the end of an array static void pushBinaryToBorder( int arr[], int n) { // To store the count of elements // which are not equal to 1 int count1 = 0 ; // Traverse the array and calculate // count of elements which are not 1 for ( int i = 0 ; i < n; i++) if (arr[i] != 1 ) arr[count1++] = arr[i]; // Now all non-ones elements have been shifted to // front and "count1" is set as index of first 1. // Make all elements 1 from count to end. while (count1 < n) arr[count1++] = 1 ; // Initialize lastNonBinary position to zero int lastNonOne = 0 ; // Traverse the array and pull non-zero // elements to the required indices for ( int i = n - 1 ; i >= 0 ; i--) { // Ignore the 1"s if (arr[i] == 1 ) continue ; if (lastNonOne == 0 ) { // Mark the position Of // last NonBinary integer lastNonOne = i; } // Place non-zero element to // their required indices if (arr[i] != 0 ) arr[lastNonOne--] = arr[i]; } // Put zeros to start of array while (lastNonOne >= 0 ) arr[lastNonOne--] = 0 ; } // Driver code public static void main(String args[]) { int arr[] = { 1 , 2 , 0 , 0 , 0 , 3 , 6 }; int n = arr.length; pushBinaryToBorder(arr, n); printArr(arr, n); } } // This code is contributed by SURENDRA_GANGWAR. |
Python3
# Python3 implementation of the approach # Utility function to print # the contenets of an array def printArr(arr, n) : for i in range (n) : print (arr[i],end = " " ) # Function that pushes all the zeros # to the start and ones to the end of an array def pushBinaryToBorder(arr, n) : # To store the count of elements # which are not equal to 1 count1 = 0 # Traverse the array and calculate # count of elements which are not 1 for i in range (n) : if (arr[i] ! = 1 ) : arr[count1] = arr[i] count1 + = 1 # Now all non-ones elements have been shifted to # front and "count1" is set as index of first 1. # Make all elements 1 from count to end. while (count1 < n) : arr[count1] = 1 count1 + = 1 # Initialize lastNonBinary position to zero lastNonOne = 0 # Traverse the array and pull non-zero # elements to the required indices for i in range (n - 1 , - 1 , - 1 ) : # Ignore the 1"s if (arr[i] = = 1 ) : continue if ( not lastNonOne) : # Mark the position Of # last NonBinary integer lastNonOne = i # Place non-zero element to # their required indices if (arr[i] ! = 0 ) : arr[lastNonOne] = arr[i] lastNonOne - = 1 # Put zeros to start of array while (lastNonOne > = 0 ) : arr[lastNonOne] = 0 lastNonOne - = 1 # Driver code if __name__ = = "__main__" : arr = [ 1 , 2 , 0 , 0 , 0 , 3 , 6 ]; n = len (arr); pushBinaryToBorder(arr, n) printArr(arr, n) # This code is contributed by Ryuga |
C#
// C# implementation of the approach using System; class GFG { // Utility function to print // the contenets of an array static void printArr( int []arr, int n) { for ( int i = 0; i < n; i++) Console.Write(arr[i] + " " ); } // Function that pushes all the zeros // to the start and ones to the end of an array static void pushBinaryToBorder( int [] arr, int n) { // To store the count of elements // which are not equal to 1 int count1 = 0; // Traverse the array and calculate // count of elements which are not 1 for ( int i = 0; i < n; i++) if (arr[i] != 1) arr[count1++] = arr[i]; // Now all non-ones elements have been shifted to // front and "count1" is set as index of first 1. // Make all elements 1 from count to end. while (count1 < n) arr[count1++] = 1; // Initialize lastNonBinary position to zero int lastNonOne = 0; // Traverse the array and pull non-zero // elements to the required indices for ( int i = n - 1; i >= 0; i--) { // Ignore the 1"s if (arr[i] == 1) continue ; if (lastNonOne == 0) { // Mark the position Of // last NonBinary integer lastNonOne = i; } // Place non-zero element to // their required indices if (arr[i] != 0) arr[lastNonOne--] = arr[i]; } // Put zeros to start of array while (lastNonOne >= 0) arr[lastNonOne--] = 0; } // Driver code public static void Main() { int []arr = { 1, 2, 0, 0, 0, 3, 6 }; int n = arr.Length; pushBinaryToBorder(arr, n); printArr(arr, n); } } // This code is contributed by Mohit kumar 29. |
Javascript
<script> // Javascript implementation of the approach // Utility function to print // the contenets of an array function printArr(arr, n) { for ( var i = 0; i < n; i++) document.write( arr[i] + " " ); } // Function that pushes all the zeros // to the start and ones to the end of an array function pushBinaryToBorder(arr, n) { // To store the count of elements // which are not equal to 1 var count1 = 0; // Traverse the array and calculate // count of elements which are not 1 for ( var i = 0; i < n; i++) if (arr[i] != 1) arr[count1++] = arr[i]; // Now all non-ones elements have been shifted to // front and "count1" is set as index of first 1. // Make all elements 1 from count to end. while (count1 < n) arr[count1++] = 1; // Initialize lastNonBinary position to zero var lastNonOne = 0; // Traverse the array and pull non-zero // elements to the required indices for ( var i = n - 1; i >= 0; i--) { // Ignore the 1"s if (arr[i] == 1) continue ; if (!lastNonOne) { // Mark the position Of // last NonBinary integer lastNonOne = i; } // Place non-zero element to // their required indices if (arr[i] != 0) arr[lastNonOne--] = arr[i]; } // Put zeros to start of array while (lastNonOne >= 0) arr[lastNonOne--] = 0; } // Driver code var arr = [ 1, 2, 0, 0, 0, 3, 6 ]; var n = arr.length; pushBinaryToBorder(arr, n); printArr(arr, n); </script> |
0 0 0 2 3 6 1
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.