ארגן מחדש רשימה נתונה כך שהיא מורכבת ממרכיבי מינימום מקסימום לסירוגין

נסה את זה ב-GfG Practice

#practiceLinkDiv { display: none !חשוב; }

בהינתן רשימה של מספרים שלמים, ארגן מחדש את הרשימה כך שהיא מורכבת ממרכיבי מינימום מקסימום לסירוגין באמצעות פעולות רשימה בלבד . הרכיב הראשון ברשימה צריך להיות מינימום והרכיב השני צריך להיות מקסימום מכל הרכיבים הקיימים ברשימה. באופן דומה האלמנט השלישי יהיה האלמנט המינימלי הבא והאלמנט הרביעי הוא האלמנט המקסימלי הבא וכן הלאה. אסור להשתמש בחלל נוסף. דוגמאות:

    Input:      [1 3 8 2 7 5 6 4]   
    Output:     [1 8 2 7 3 6 4 5]   
    Input:      [1 2 3 4 5 6 7]   
    Output:     [1 7 2 6 3 5 4]   
    Input:      [1 6 2 5 3 4]   
    Output:     [1 6 2 5 3 4]   
Recommended Practice  ארגון מחדש של מערך    נסה את זה!    הרעיון הוא קודם כל למיין את הרשימה בסדר עולה. לאחר מכן אנו מתחילים להקפיץ אלמנטים מסוף הרשימה ולהכניס אותם למקומם הנכון ברשימה. להלן יישום הרעיון לעיל -   
 C++      // C++ program to rearrange a given list such that it    // consists of alternating minimum maximum elements    #include             using     namespace     std  ;      // Function to rearrange a given list such that it    // consists of alternating minimum maximum elements    void     alternateSort  (  list   <  int  >&     inp  )      {         // sort the list in ascending order       inp  .  sort  ();         // get iterator to first element of the list       list   <  int  >::  iterator     it     =     inp  .  begin  ();         it  ++  ;         for     (  int     i  =  1  ;     i   <  (  inp  .  size  ()     +     1  )  /  2  ;     i  ++  )         {         // pop last element (next greatest)       int     val     =     inp  .  back  ();         inp  .  pop_back  ();         // insert it after next minimum element       inp  .  insert  (  it       val  );         // increment the pointer for next pair       ++  it  ;         }      }      // Driver code    int     main  ()      {         // input list       list   <  int  >     inp  ({     1       3       8       2       7       5       6       4     });         // rearrange the given list       alternateSort  (  inp  );         // print the modified list       for     (  int     i     :     inp  )         cout      < <     i      < <     ' '  ;         return     0  ;      }      
  Java      // Java program to rearrange a given list such that it   // consists of alternating minimum maximum elements   import     java.util.*  ;   class   AlternateSort   {      // Function to rearrange a given list such that it      // consists of alternating minimum maximum elements      // using LinkedList      public     static     void     alternateSort  (  LinkedList   <  Integer  >     ll  )         {      Collections  .  sort  (  ll  );          for     (  int     i     =     1  ;     i      <     (  ll  .  size  ()     +     1  )  /  2  ;     i  ++  )      {      Integer     x     =     ll  .  getLast  ();      ll  .  removeLast  ();      ll  .  add  (  2  *  i     -     1       x  );      }          System  .  out  .  println  (  ll  );      }          public     static     void     main     (  String  []     args  )     throws     java  .  lang  .  Exception      {      // input list      Integer     arr  []     =     {  1       3       8       2       7       5       6       4  };          // convert array to LinkedList      LinkedList   <  Integer  >     ll     =     new     LinkedList   <  Integer  >  (  Arrays  .  asList  (  arr  ));          // rearrange the given list      alternateSort  (  ll  );      }   }   
  Python      # Python program to rearrange a given list such that it   # consists of alternating minimum maximum elements   inp   =   []   # Function to rearrange a given list such that it   # consists of alternating minimum maximum elements   def   alternateSort  ():   global   inp   # sort the list in ascending order   inp  .  sort  ()   # get index to first element of the list   it   =   0   it   =   it   +   1   i   =   1   while   (   i    <   (  len  (  inp  )   +   1  )  /  2   ):   i   =   i   +   1   # pop last element (next greatest)   val   =   inp  [  -  1  ]   inp  .  pop  ()   # insert it after next minimum element   inp  .  insert  (  it     val  )   # increment the pointer for next pair   it   =   it   +   2   # Driver code   # input list   inp  =  [   1     3     8     2     7     5     6     4   ]   # rearrange the given list   alternateSort  ()   # print the modified list   print   (  inp  )   # This code is contributed by Arnab Kundu   
  C#      // C# program to rearrange a given list such that it   // consists of alternating minimum maximum elements    using     System  ;      using     System.Collections.Generic  ;   class     GFG   {      // Function to rearrange a given list such that it      // consists of alternating minimum maximum elements      // using List      public     static     void     alternateSort  (  List   <  int  >     ll  )         {      ll  .  Sort  ();          for     (  int     i     =     1  ;     i      <     (  ll  .  Count     +     1  )  /  2  ;     i  ++  )      {      int     x     =     ll  [  ll  .  Count  -  1  ];      ll  .  RemoveAt  (  ll  .  Count  -  1  );      ll  .  Insert  (  2  *  i     -     1       x  );      }      foreach  (  int     a     in     ll  )      {      Console  .  Write  (  a  +  ' '  );      }          }          // Driver code      public     static     void     Main     (  String  []     args  )      {      // input list      int     []  arr     =     {  1       3       8       2       7       5       6       4  };          // convert array to List      List   <  int  >     ll     =     new     List   <  int  >  (  arr  );          // rearrange the given list      alternateSort  (  ll  );      }   }   /* This code contributed by PrinciRaj1992 */   
  JavaScript       <  script  >   // JavaScript program to rearrange a given list such that it   // consists of alternating minimum maximum elements   let     inp     =     []   // Function to rearrange a given list such that it   // consists of alternating minimum maximum elements   function     alternateSort  (){      // sort the list in ascending order      inp  .  sort  ()      // get index to first element of the list      let     it     =     0      it     =     it     +     1          let     i     =     1          while     (     i      <     (  inp  .  length     +     1  )  /  2     ){          i     =     i     +     1          // pop last element (next greatest)      let     val     =     inp  [  inp  .  length  -  1  ]      inp  .  pop  ()      // insert it after next minimum element      inp  .  splice  (  it    0       val  )      // increment the pointer for next pair      it     =     it     +     2      }   }       // Driver code   // input list   inp  =  [     1       3       8       2       7       5       6       4     ]   // rearrange the given list   alternateSort  ()   // print the modified list   for  (  let     x     of     inp  ){      document  .  write  (  x    ' '  )   }   // This code is contributed by shinjanpatra    <  /script>   
    
  תְפוּקָה   1 8 2 7 3 6 4 5  
     מורכבות זמן:    O(N*logN) מכיוון שאנו משתמשים בפונקציית מיון.   
    מרחב עזר:    O(1) מכיוון שאיננו משתמשים בחלל נוסף.  
      
   גישה מס' 2: שימוש במיון()  
  מיין את הרשימה הנתונה בסדר עולה אתחול רשימת תוצאות ריקה חזור על מחצית מדדי הרשימה הממוינים: הוסף את האלמנט מהאינדקס הנוכחי ואת האלמנט המתאים מסוף הרשימה אם אורך הרשימה המקורית אי זוגי הוסף את האלמנט האמצעי לרשימת התוצאות המר את רשימת התוצאות למחרוזת עם מספרים שלמים מופרדים ברווחים  
   אַלגוֹרִיתְם  
  1. מיין את הרשימה באמצעות הפונקציה sort()    
 2. אתחול רשימת תוצאות ריקה   
 3. עברו בלולאה בטווח של המחצית הראשונה של הרשימה   
 4. הוסף את האלמנט ה-i של הרשימה הממוינת   
 5. הוסף את האלמנט (-i-1)-th של הרשימה הממוינת   
 6. אם אורכה של הרשימה המקורית מוזר, הוסף את האלמנט האמצעי לרשימת התוצאות   
 7. המר את רשימת התוצאות למחרוזת באמצעות הפונקציה join()   
 C++      #include          #include          #include         using     namespace     std  ;   string     alternateMinMax  (  vector   <  int  >     lst  )     {      sort  (  lst  .  begin  ()     lst  .  end  ());      vector   <  int  >     res  ;      for     (  int     i     =     0  ;     i      <     lst  .  size  ()     /     2  ;     i  ++  )     {      res  .  push_back  (  lst  [  i  ]);      res  .  push_back  (  lst  [  lst  .  size  ()     -     i     -     1  ]);      }      if     (  lst  .  size  ()     %     2     ==     1  )     {      res  .  push_back  (  lst  [  lst  .  size  ()     /     2  ]);      }      string     result     =     ''  ;      for     (  int     i     =     0  ;     i      <     res  .  size  ();     i  ++  )     {      result     +=     to_string  (  res  [  i  ])     +     ' '  ;      }      return     result  ;   }   int     main  ()     {      vector   <  int  >     lst     =     {  1       3       8       2       7       5       6       4  };      cout      < <     alternateMinMax  (  lst  )      < <     endl  ;      return     0  ;   }   
  Java      import     java.util.ArrayList  ;   import     java.util.Collections  ;   import     java.util.List  ;   public     class   AlternateMinMax     {      // Function to rearrange a list of integers in alternating min-max order      public     static     String     alternateMinMax  (  List   <  Integer  >     lst  )     {      // Sort the input list in ascending order      Collections  .  sort  (  lst  );              List   <  Integer  >     res     =     new     ArrayList   <>  ();          // Iterate through the first half of the sorted list      for     (  int     i     =     0  ;     i      <     lst  .  size  ()     /     2  ;     i  ++  )     {          res  .  add  (  lst  .  get  (  i  ));      res  .  add  (  lst  .  get  (  lst  .  size  ()     -     i     -     1  ));      }          // If the input list has an odd number of elements add the middle element      if     (  lst  .  size  ()     %     2     ==     1  )     {      res  .  add  (  lst  .  get  (  lst  .  size  ()     /     2  ));      }          // Create a StringBuilder to build the result string      StringBuilder     result     =     new     StringBuilder  ();          // Append each element from the rearranged list to the result string      for     (  int     i     =     0  ;     i      <     res  .  size  ();     i  ++  )     {      result  .  append  (  res  .  get  (  i  )).  append  (  ' '  );      }              return     result  .  toString  ();      }      public     static     void     main  (  String  []     args  )     {      // Create a list of integers      List   <  Integer  >     lst     =     new     ArrayList   <>  ();      lst  .  add  (  1  );      lst  .  add  (  3  );      lst  .  add  (  8  );      lst  .  add  (  2  );      lst  .  add  (  7  );      lst  .  add  (  5  );      lst  .  add  (  6  );      lst  .  add  (  4  );          // Call the alternateMinMax function and print the result      System  .  out  .  println  (  alternateMinMax  (  lst  ));      }   }   
  Python3      def   alternate_min_max  (  lst  ):   lst  .  sort  ()   res   =   []   for   i   in   range  (  len  (  lst  )   //   2  ):   res  .  append  (  lst  [  i  ])   res  .  append  (  lst  [  -  i  -  1  ])   if   len  (  lst  )   %   2   ==   1  :   res  .  append  (  lst  [  len  (  lst  )   //   2  ])   return   ' '  .  join  (  map  (  str     res  ))   lst   =   [  1     3     8     2     7     5     6     4  ]   print  (  alternate_min_max  (  lst  ))   
  C#      using     System  ;   using     System.Collections.Generic  ;   using     System.Linq  ;   public     class     GFG   {      public     static     string     GetAlternateMinMax  (  List   <  int  >     lst  )      {      // Sort the list in ascending order      lst  .  Sort  ();      List   <  int  >     res     =     new     List   <  int  >  ();      int     n     =     lst  .  Count  ;      // Create the alternating min-max list      for     (  int     i     =     0  ;     i      <     n     /     2  ;     i  ++  )      {      res  .  Add  (  lst  [  i  ]);      res  .  Add  (  lst  [  n     -     i     -     1  ]);      }      // If the list has an odd number of elements add the middle element      if     (  n     %     2     ==     1  )      {      res  .  Add  (  lst  [  n     /     2  ]);      }      // Convert the result list to a string      string     result     =     string  .  Join  (  ' '       res  );      return     result  ;      }      public     static     void     Main  (  string  []     args  )      {      List   <  int  >     lst     =     new     List   <  int  >     {     1       3       8       2       7       5       6       4     };      string     result     =     GetAlternateMinMax  (  lst  );      Console  .  WriteLine  (  result  );      }   }   
  JavaScript      function     alternateMinMax  (  lst  )     {      lst  .  sort  ((  a       b  )     =>     a     -     b  );      // Initialize an empty array to       // store the result      const     res     =     [];      for     (  let     i     =     0  ;     i      <     Math  .  floor  (  lst  .  length     /     2  );     i  ++  )     {      // Push the minimum element from the beginning      res  .  push  (  lst  [  i  ]);      res  .  push  (  lst  [  lst  .  length     -     i     -     1  ]);      }      // If the length of the list is odd      // push the middle element      if     (  lst  .  length     %     2     ===     1  )     {      res  .  push  (  lst  [  Math  .  floor  (  lst  .  length     /     2  )]);      }      // Convert the result array to a       // space-separated string      const     result     =     res  .  join  (  ' '  );      return     result  ;   }   // Input list   const     lst     =     [  1       3       8       2       7       5       6       4  ];   console  .  log  (  alternateMinMax  (  lst  ));   
    
  תְפוּקָה   1 8 2 7 3 6 4 5 
  מורכבות זמן: O(nlogn) בגלל פעולת המיון. לולאת for חוזרת על פני מחצית מהרשימה, מה שלוקח זמן O(n/2). ההמרה של רשימת התוצאות למחרוזת לוקחת זמן O(n). מכיוון ש-O(nlogn) גדול מ-O(n), מורכבות הזמן הכוללת היא O(n*logn).  
   רווח עזר: O(n) מכיוון שהרשימה הממוינת ורשימת התוצאות תופסות רווח O(n). הרווח המשמש את המשתנים המשמשים בפונקציה הוא קבוע ואינו תלוי בגודל רשימת הקלט.