将所有零移到数组末尾-yiteyi-C++库

给定一个随机数数组，将给定数组的所有零推到数组的末尾。例如，如果给定的数组是{1,9,8,4,0,0,2,7,0,6,0}，则应该将其更改为{1,9,8,4,2,7,6,0,0,0,0}。所有其他元素的顺序应该相同。预期时间复杂度为O（n），额外空间为O（1）。 例子：

null

Input :  arr[] = {1, 2, 0, 4, 3, 0, 5, 0};Output : arr[] = {1, 2, 4, 3, 5, 0, 0, 0};Input : arr[]  = {1, 2, 0, 0, 0, 3, 6};Output : arr[] = {1, 2, 3, 6, 0, 0, 0};

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

有很多方法可以解决这个问题。下面是一个简单而有趣的方法来解决这个问题。从左向右遍历给定数组“arr”。遍历时，保持数组中非零元素的计数。让计数成为“计数”。对于每个非零元素arr[i]，将元素置于“arr[count]”并递增“count”。在完成遍历之后，所有非零元素都已经被转移到前端，“count”被设置为前0的索引。现在我们需要做的就是运行一个循环，使所有元素从“count”到数组末尾都为零。以下是上述方法的实施情况。

C

                         // A C program to move all zeroes at the end of array                       
                         #include <stdio.h>                       
           
                         // Function which pushes all zeros to end of an array.                       
                         void                                     pushZerosToEnd(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 int                                     count = {0};                                     // Count of non-zero elements                       
           
                                                 // Traverse the array. If element encountered is non-                       
                                                 // zero, then replace the element at index 'count'                       
                                                 // with this element                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 if                                     (arr[i] != 0)                       
                                                 arr[count++] = arr[i];                                     // here count is                       
                                                 // incremented                       
           
                                                 // Now all non-zero elements have been shifted to                       
                                                 // front and  'count' is set as index of first 0.                       
                                                 // Make all elements 0 from count to end.                       
                                                 while                                     (count < n)                       
                                                 arr[count++] = 0;                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9};                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 pushZerosToEnd(arr, n);                       
                                                 printf                                     (                                     "%s"                                     ,                                     "Array after pushing all zeros to end of array:"                                     );                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 printf                                     (                                     "%d "                                     , arr[i]);                       
                                                 return                                     0;                       
                         }                       

C++

                         #include <algorithm>                       
                         #include <iostream>                       
                         #include <vector>                       
           
                         void                                     push_zeros_to_end(std::vector<                                     int                                     >& arr)                       
                         {                       
                                                 std::stable_partition(arr.begin(),                       
                                                 arr.end(),                       
                                                 [](                                     int                                     n) {                                     return                                     n != 0; });                       
                         }                       
           
                         int                                     main()                       
                         {                       
                                                 std::vector<                                     int                                     > arr{1,9,8,4,0,0,2,7,0,6,0,9};                       
                                   
                                                 push_zeros_to_end(arr);                       
                                   
                                                 for                                     (                                     const                                     auto                                     & i : arr)                       
                                                 std::cout << i <<                                     ' '                                     ;                       
           
                                                 std::cout <<                                     ""                                     ;                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         /* Java program to push zeroes to back of array */                       
                         import                                     java.io.*;                       
           
                         class                                     PushZero                       
                         {                       
                                                 // Function which pushes all zeros to end of an array.                       
                                                 static                                     void                                     pushZerosToEnd(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 int                                     count =                                     0                                     ;                                     // Count of non-zero elements                       
           
                                                 // Traverse the array. If element encountered is                       
                                                 // non-zero, then replace the element at index 'count'                       
                                                 // with this element                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 if                                     (arr[i] !=                                     0                                     )                       
                                                 arr[count++] = arr[i];                                     // here count is                       
                                                 // incremented                       
           
                                                 // Now all non-zero elements have been shifted to                       
                                                 // front and 'count' is set as index of first 0.                       
                                                 // Make all elements 0 from count to end.                       
                                                 while                                     (count < n)                       
                                                 arr[count++] =                                     0                                     ;                       
                                                 }                       
           
                                                 /*Driver function to check for above functions*/                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     1                                     ,                                     9                                     ,                                     8                                     ,                                     4                                     ,                                     0                                     ,                                     0                                     ,                                     2                                     ,                                     7                                     ,                                     0                                     ,                                     6                                     ,                                     0                                     ,                                     9                                     };                       
                                                 int                                     n = arr.length;                       
                                                 pushZerosToEnd(arr, n);                       
                                                 System.out.println(                                     "Array after pushing zeros to the back: "                                     );                       
                                                 for                                     (                                     int                                     i=                                     0                                     ; i<n; i++)                       
                                                 System.out.print(arr[i]+                                     " "                                     );                       
                                                 }                       
                         }                       
                         /* This code is contributed by Devesh Agrawal */                       

Python3

                         # Python3 code to move all zeroes                       
                         # at the end of array                       
           
                         # Function which pushes all                       
                         # zeros to end of an array.                       
                         def                                     pushZerosToEnd(arr, n):                       
                                                 count                                     =                                     0                                     # Count of non-zero elements                       
                                   
                                                 # Traverse the array. If element                       
                                                 # encountered is non-zero, then                       
                                                 # replace the element at index                       
                                                 # 'count' with this element                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 if                                     arr[i] !                                     =                                     0                                     :                       
                                   
                                                 # here count is incremented                       
                                                 arr[count]                                     =                                     arr[i]                       
                                                 count                                     +                                     =                                     1                       
                                   
                                                 # Now all non-zero elements have been                       
                                                 # shifted to front and 'count' is set                       
                                                 # as index of first 0. Make all                       
                                                 # elements 0 from count to end.                       
                                                 while                                     count < n:                       
                                                 arr[count]                                     =                                     0                       
                                                 count                                     +                                     =                                     1                       
                                   
                         # Driver code                       
                         arr                                     =                                     [                                     1                                     ,                                     9                                     ,                                     8                                     ,                                     4                                     ,                                     0                                     ,                                     0                                     ,                                     2                                     ,                                     7                                     ,                                     0                                     ,                                     6                                     ,                                     0                                     ,                                     9                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         pushZerosToEnd(arr, n)                       
                         print                                     (                                     "Array after pushing all zeros to end of array:"                                     )                       
                         print                                     (arr)                       
           
                         # This code is contributed by "Abhishek Sharma 44"                       

C#

                         /* C# program to push zeroes to back of array */                       
                         using                                     System;                       
           
                         class                                     PushZero                       
                         {                       
                                                 // Function which pushes all zeros                       
                                                 // to end of an array.                       
                                                 static                                     void                                     pushZerosToEnd(                                     int                                     []arr,                                     int                                     n)                       
                                                 {                       
                                                 // Count of non-zero elements                       
                                                 int                                     count = 0;                       
                                   
                                                 // Traverse the array. If element encountered is                       
                                                 // non-zero, then replace the element                       
                                                 // at index â..countâ.. with this element                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 if                                     (arr[i] != 0)                       
                                   
                                                 // here count is incremented                       
                                                 arr[count++] = arr[i];                       
                                   
                                                 // Now all non-zero elements have been shifted to                       
                                                 // front and â..countâ.. is set as index of first 0.                       
                                                 // Make all elements 0 from count to end.                       
                                                 while                                     (count < n)                       
                                                 arr[count++] = 0;                       
                                                 }                       
                                   
                                                 // Driver function                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     []arr = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9};                       
                                                 int                                     n = arr.Length;                       
                                                 pushZerosToEnd(arr, n);                       
                                                 Console.WriteLine(                                     "Array after pushing all zeros to the back: "                                     );                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 Console.Write(arr[i] +                                     " "                                     );                       
                                                 }                       
                         }                       
                         /* This code is contributed by Anant Agrawal */                       

PHP

                         <?php                       
                         // A PHP program to move all                       
                         // zeroes at the end of array                       
           
                         // Function which pushes all                       
                         // zeros to end of an array.                       
                         function                                     pushZerosToEnd(&                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 // Count of non-zero elements                       
                                                 $count                                     = 0;                       
           
                                                 // Traverse the array. If                       
                                                 // element encountered is                       
                                                 // non-zero, then replace                       
                                                 // the element at index                       
                                                 // 'count' with this element                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 if                                     (                                     $arr                                     [                                     $i                                     ] != 0)                       
                                                 // here count is incremented                       
                                                 $arr                                     [                                     $count                                     ++] =                                     $arr                                     [                                     $i                                     ];                       
           
                                                 // Now all non-zero elements                       
                                                 // have been shifted to front                       
                                                 // and 'count' is set as index                       
                                                 // of first 0. Make all elements                       
                                                 // 0 from count to end.                       
                                                 while                                     (                                     $count                                     <                                     $n                                     )                       
                                                 $arr                                     [                                     $count                                     ++] = 0;                       
                         }                       
           
                         // Driver Code                       
                         $arr                                     =                                     array                                     (1, 9, 8, 4, 0, 0,                       
                                                 2, 7, 0, 6, 0, 9);                       
                         $n                                     = sizeof(                                     $arr                                     );                       
                         pushZerosToEnd(                                     $arr                                     ,                                     $n                                     );                       
                         echo                                     "Array after pushing all "                                     .                       
                                                 "zeros to end of array :"                                     ;                       
           
                         for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                         echo                                     $arr                                     [                                     $i                                     ] .                                     " "                                     ;                       
           
                         // This code is contributed                       
                         // by ChitraNayal                       
                         ?>                       

Javascript

                         <script>                       
                         // A JavaScript program to move all zeroes at the end of array                       
           
                         // Function which pushes all zeros to end of an array.                       
                         function                                     pushZerosToEnd(arr, n)                       
                         {                       
                                                 let count = 0;                                     // Count of non-zero elements                       
           
                                                 // Traverse the array. If element encountered is non-                       
                                                 // zero, then replace the element at index 'count'                       
                                                 // with this element                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 if                                     (arr[i] != 0)                       
                                                 arr[count++] = arr[i];                                     // here count is                       
                                                 // incremented                       
           
                                                 // Now all non-zero elements have been shifted to                       
                                                 // front and 'count' is set as index of first 0.                       
                                                 // Make all elements 0 from count to end.                       
                                                 while                                     (count < n)                       
                                                 arr[count++] = 0;                       
                         }                       
           
                         // Driver code                       
                                                 let arr = [1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9];                       
                                                 let n = arr.length;                       
                                                 pushZerosToEnd(arr, n);                       
                                                 document.write(                                     "Array after pushing all zeros to end of array :<br>"                                     );                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 document.write(arr[i] +                                     " "                                     );                       
           
                         // This code is contributed by Surbhi Tyagi.                       
                         </script>                       

输出

Array after pushing all zeros to end of array :1 9 8 4 2 7 6 9 0 0 0 0

输出：

Array after pushing all zeros to end of array :1 9 8 4 2 7 6 9 0 0 0 0

时间复杂性： O（n），其中n是输入数组中的元素数。 辅助空间： O（1）

本文由 钱德拉·普拉卡什 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章