Pārkārtojiet doto sarakstu tā, lai tas sastāvētu no mainīgiem minimālajiem maksimālajiem elementiem
Izmēģiniet to GfG Practice 
#practiceLinkDiv { display: none !important; }
#practiceLinkDiv { display: none !important; } Ņemot vērā veselu skaitļu sarakstu, pārkārtojiet sarakstu tā, lai tas sastāvētu no mainīgiem minimālajiem maksimālajiem elementiem izmantojot tikai saraksta darbības . Saraksta pirmajam elementam jābūt minimālam, bet otrajam elementam jābūt maksimālajam no visiem sarakstā esošajiem elementiem. Līdzīgi trešais elements būs nākamais minimālais elements un ceturtais elements ir nākamais maksimālais elements un tā tālāk. Papildu vietas izmantošana nav atļauta. Piemēri:
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 Masīva pārkārtošana Izmēģiniet to!Ideja ir vispirms sakārtot sarakstu augošā secībā. Pēc tam mēs sākam parādīt elementus no saraksta beigām un ievietojam tos pareizajā sarakstā. Zemāk ir iepriekš minētās idejas īstenošana -
C++Java// C++ program to rearrange a given list such that it // consists of alternating minimum maximum elements #includeusing 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 ; } Python// 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 ); } }C## 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 KunduJavaScript// 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 */
Izvade1 8 2 7 3 6 4 5Laika sarežģītība: O(N*logN), jo mēs izmantojam kārtošanas funkciju.
Palīgtelpa: O(1), jo mēs neizmantojam papildu vietu.
2. pieeja: Sort() izmantošana
Kārtot doto sarakstu augošā secībā Inicializēt tukšu rezultātu sarakstu Iterēt vairāk nekā pusi no sakārtotā saraksta indeksiem: pievienot elementu no pašreizējā indeksa un atbilstošo elementu no saraksta beigām Ja sākotnējā saraksta garums ir nepāra pievienot vidējo elementu rezultātu sarakstam Pārvērst rezultātu sarakstu par virkni ar atstarpi atdalītiem veseliem skaitļiem
Algoritms
1. Kārtojiet sarakstu, izmantojot funkciju sort().
C++
2. Inicializējiet tukšu rezultātu sarakstu
3. Pārlūkojiet saraksta pirmās puses diapazonu
4. Pievienojiet sakārtotā saraksta i-to elementu
5. Pievienojiet sakārtotā saraksta elementu (-i-1).
6. Ja sākotnējā saraksta garums ir nepāra, pievienojiet vidējo elementu rezultātu sarakstam
7. Pārveidojiet rezultātu sarakstu par virkni, izmantojot funkciju join().Java#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 ; } Python3import 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 )); } }C#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 ))JavaScriptusing 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 ); } }
Izvade1 8 2 7 3 6 4 5Laika sarežģītība: O (nlogn) šķirošanas darbības dēļ. For cilpa atkārto vairāk nekā pusi no saraksta, kas aizņem O(n/2) laiku. Rezultātu saraksta pārvēršana virknē aizņem O(n) laiku. Tā kā O(nlogn) ir lielāks par O(n), kopējā laika sarežģītība ir O(n*logn).
Papildtelpa: O(n), jo gan sakārtotais saraksts, gan rezultātu saraksts aizņem O(n) vietu. Vieta, ko izmanto funkcijā izmantotie mainīgie, ir nemainīga un nav atkarīga no ievades saraksta lieluma.
