以最大最小形式重新排列数组|集1-yiteyi-C++库

给定一个正整数排序数组，交替重新排列数组，即第一个元素应为最大值、第二个最小值、第三个最大值、第四个最小值，依此类推。

null

例如：

输入：arr[]={1,2,3,4,5,6,7} 输出：arr[]={7,1,6,2,5,3,4}

输入：arr[]={1,2,3,4,5,6} 输出：arr[]={6,1,5,2,4,3}

预期时间复杂度：O（n）。

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

这个想法是使用一个辅助阵列。我们维护两个指针，一个指向最左边或最小的元素，另一个指向最右边或最大的元素。我们将两个指针相互移动，或者将这些指针上的元素复制到一个辅助数组。最后，我们将辅助数组复制回原始数组。

下图是上述方法的试运行：

图片[1]-以最大最小形式重新排列数组|集1-yiteyi-C++库

以下是上述方法的实施情况：

C++

                         // C++ program to rearrange an array in minimum                       
                         // maximum form                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Prints max at first position, min at second position                       
                         // second max at third position, second min at fourth                       
                         // position and so on.                       
                         void                                     rearrange(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // Auxiliary array to hold modified array                       
                                                 int                                     temp[n];                       
           
                                                 // Indexes of smallest and largest elements                       
                                                 // from remaining array.                       
                                                 int                                     small = 0, large = n - 1;                       
           
                                                 // To indicate whether we need to copy remaining                       
                                                 // largest or remaining smallest at next position                       
                                                 int                                     flag =                                     true                                     ;                       
           
                                                 // Store result in temp[]                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 if                                     (flag)                       
                                                 temp[i] = arr[large--];                       
                                                 else                       
                                                 temp[i] = arr[small++];                       
           
                                                 flag = !flag;                       
                                                 }                       
           
                                                 // Copy temp[] to arr[]                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 arr[i] = temp[i];                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 1, 2, 3, 4, 5, 6 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
           
                                                 cout <<                                     "Original Array"                                     ;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 cout << arr[i] <<                                     " "                                     ;                       
           
                                                 rearrange(arr, n);                       
           
                                                 cout <<                                     "Modified Array"                                     ;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 cout << arr[i] <<                                     " "                                     ;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to rearrange an array in minimum                       
                         // maximum form                       
           
                         import                                     java.util.Arrays;                       
           
                         public                                     class                                     GFG                       
                         {                       
                                                 // Prints max at first position, min at second position                       
                                                 // second max at third position, second min at fourth                       
                                                 // position and so on.                       
                                                 static                                     void                                     rearrange(                                     int                                     [] arr,                                     int                                     n)                       
                                                 {                       
                                                 // Auxiliary array to hold modified array                       
                                                 int                                     temp[] = arr.clone();                       
           
                                                 // Indexes of smallest and largest elements                       
                                                 // from remaining array.                       
                                                 int                                     small =                                     0                                     , large = n -                                     1                                     ;                       
           
                                                 // To indicate whether we need to copy remaining                       
                                                 // largest or remaining smallest at next position                       
                                                 boolean                                     flag =                                     true                                     ;                       
           
                                                 // Store result in temp[]                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
                                                 if                                     (flag)                       
                                                 arr[i] = temp[large--];                       
                                                 else                       
                                                 arr[i] = temp[small++];                       
           
                                                 flag = !flag;                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] =                                     new                                     int                                     [] {                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     ,                                     6                                     };                       
           
                                                 System.out.println(                                     "Original Array "                                     );                       
                                                 System.out.println(Arrays.toString(arr));                       
           
                                                 rearrange(arr, arr.length);                       
           
                                                 System.out.println(                                     "Modified Array "                                     );                       
                                                 System.out.println(Arrays.toString(arr));                       
                                                 }                       
                         }                       

Python3

                         # Python program to rearrange an array in minimum                       
                         # maximum form                       
           
                         # Prints max at first position, min at second position                       
                         # second max at third position, second min at fourth                       
                         # position and so on.                       
           
           
                         def                                     rearrange(arr, n):                       
                                                 # Auxiliary array to hold modified array                       
                                                 temp                                     =                                     n                                     *                                     [                                     None                                     ]                       
           
                                                 # Indexes of smallest and largest elements                       
                                                 # from remaining array.                       
                                                 small, large                                     =                                     0                                     , n                                     -                                     1                       
           
                                                 # To indicate whether we need to copy remaining                       
                                                 # largest or remaining smallest at next position                       
                                                 flag                                     =                                     True                       
           
                                                 # Store result in temp[]                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 if                                     flag                                     is                                     True                                     :                       
                                                 temp[i]                                     =                                     arr[large]                       
                                                 large                                     -                                     =                                     1                       
                                                 else                                     :                       
                                                 temp[i]                                     =                                     arr[small]                       
                                                 small                                     +                                     =                                     1                       
           
                                                 flag                                     =                                     bool                                     (                                     1                                     -                                     flag)                       
           
                                                 # Copy temp[] to arr[]                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 arr[i]                                     =                                     temp[i]                       
                                                 return                                     arr                       
           
           
                         # Driver code                       
                         arr                                     =                                     [                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     ,                                     6                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         print                                     (                                     "Original Array"                                     )                       
                         print                                     (arr)                       
                         print                                     (                                     "Modified Array"                                     )                       
                         print                                     (rearrange(arr, n))                       
           
                         # This code is contributed by Pratik Chhajer                       

C#

                         // C# program to rearrange                       
                         // an array in minimum                       
                         // maximum form                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // Prints max at first position,                       
                                                 // min at second position second                       
                                                 // max at third position, second                       
                                                 // min at fourth position and so on.                       
                                                 static                                     void                                     rearrange(                                     int                                     [] arr,                                     int                                     n)                       
                                                 {                       
                                                 // Auxiliary array to                       
                                                 // hold modified array                       
                                                 int                                     [] temp =                                     new                                     int                                     [n];                       
           
                                                 // Indexes of smallest                       
                                                 // and largest elements                       
                                                 // from remaining array.                       
                                                 int                                     small = 0, large = n - 1;                       
           
                                                 // To indicate whether we                       
                                                 // need to copy remaining                       
                                                 // largest or remaining                       
                                                 // smallest at next position                       
                                                 bool                                     flag =                                     true                                     ;                       
           
                                                 // Store result in temp[]                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 if                                     (flag)                       
                                                 temp[i] = arr[large--];                       
                                                 else                       
                                                 temp[i] = arr[small++];                       
           
                                                 flag = !flag;                       
                                                 }                       
           
                                                 // Copy temp[] to arr[]                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 arr[i] = temp[i];                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     [] arr = { 1, 2, 3, 4, 5, 6 };                       
           
                                                 Console.WriteLine(                                     "Original Array"                                     );                       
                                                 for                                     (                                     int                                     i = 0; i < arr.Length; i++)                       
                                                 Console.Write(arr[i] +                                     " "                                     );                       
           
                                                 rearrange(arr, arr.Length);                       
           
                                                 Console.WriteLine(                                     "Modified Array"                                     );                       
                                                 for                                     (                                     int                                     i = 0; i < arr.Length; i++)                       
                                                 Console.Write(arr[i] +                                     " "                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed                       
                         // by Sam007                       

PHP

                         <?php                       
                         // PHP program to rearrange an array in                       
                         // minimum-maximum form                       
           
                         // Prints max at first position, min at                       
                         // second position second max at third                       
                         // position, second min at fourth                       
                         // position and so on.                       
                         function                                     rearrange(&                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 // Auxiliary array to hold modified array                       
                                                 $temp                                     =                                     array                                     ();                       
           
                                                 // Indexes of smallest and largest elements                       
                                                 // from remaining array.                       
                                                 $small                                     = 0;                       
                                                 $large                                     =                                     $n                                     - 1;                       
           
                                                 // To indicate whether we need to copy                       
                                                 // remaining largest or remaining smallest                       
                                                 // at next position                       
                                                 $flag                                     = true;                       
           
                                                 // Store result in temp[]                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 if                                     (                                     $flag                                     )                       
                                                 $temp                                     [                                     $i                                     ] =                                     $arr                                     [                                     $large                                     --];                       
                                                 else                       
                                                 $temp                                     [                                     $i                                     ] =                                     $arr                                     [                                     $small                                     ++];                       
           
                                                 $flag                                     = !                                     $flag                                     ;                       
                                                 }                       
           
                                                 // Copy temp[] to arr[]                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 $arr                                     [                                     $i                                     ] =                                     $temp                                     [                                     $i                                     ];                       
                         }                       
           
                         // Driver Code                       
                         $arr                                     =                                     array                                     (1, 2, 3, 4, 5, 6);                       
                         $n                                     =                                     count                                     (                                     $arr                                     );                       
           
                         echo                                     "Original Arrayn"                                     ;                       
                         for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 echo                                     $arr                                     [                                     $i                                     ] .                                     " "                                     ;                       
           
                         rearrange(                                     $arr                                     ,                                     $n                                     );                       
           
                         echo                                     "Modified Arrayn"                                     ;                       
                         for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 echo                                     $arr                                     [                                     $i                                     ] .                                     " "                                     ;                       
                                   
                         // This code is contributed by                       
                         // Rajput-Ji                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to rearrange an array in minimum                       
                         // maximum form                       
           
                         // Prints max at first position, min at second position                       
                         // second max at third position, second min at fourth                       
                         // position and so on.                       
                         function                                     rearrange(arr, n)                       
                         {                       
                                                 // Auxiliary array to hold modified array                       
                                                 let temp =                                     new                                     Array(n);                       
           
                                                 // Indexes of smallest and largest elements                       
                                                 // from remaining array.                       
                                                 let small = 0, large = n - 1;                       
           
                                                 // To indicate whether we need to copy remaining                       
                                                 // largest or remaining smallest at next position                       
                                                 let flag =                                     true                                     ;                       
           
                                                 // Store result in temp[]                       
                                                 for                                     (let i = 0; i < n; i++) {                       
                                                 if                                     (flag)                       
                                                 temp[i] = arr[large--];                       
                                                 else                       
                                                 temp[i] = arr[small++];                       
           
                                                 flag = !flag;                       
                                                 }                       
           
                                                 // Copy temp[] to arr[]                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 arr[i] = temp[i];                       
                         }                       
           
                         // Driver code                       
                                                 let arr = [ 1, 2, 3, 4, 5, 6 ];                       
                                                 let n = arr.length;                       
           
                                                 document.write(                                     "Original Array<br>"                                     );                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 document.write(arr[i] +                                     " "                                     );                       
           
                                                 rearrange(arr, n);                       
           
                                                 document.write(                                     "<br>Modified Array<br>"                                     );                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 document.write(arr[i] +                                     " "                                     );                       
           
                         // This code is contributed by Surbhi Tyagi.                       
           
                         </script>                       

输出

Original Array1 2 3 4 5 6 Modified Array6 1 5 2 4 3

时间复杂性： O（n） 辅助空间： O（n） https://youtu.be/pWASJvFqBW0?list=PLqM7alHXFySEQDk2MDfbwEdjd2svVJH9p 练习： 如果不允许额外的空间，如何解决这个问题？ 以最大最小形式重新排列数组|设置2（O（1）额外空间） 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

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

THE END

技术文章