Ordna om en given lista så att den består av alternerande minsta maxelement
#practiceLinkDiv { display: ingen !viktigt; } Givet en lista med heltal, arrangera om listan så att den består av alternerande minsta maxelement använder endast listoperationer . Det första elementet i listan bör vara minimum och det andra elementet bör vara maximum av alla element som finns i listan. På liknande sätt kommer det tredje elementet att vara nästa minimumelement och det fjärde elementet är nästa maximumelement och så vidare. Användning av extra utrymme är inte tillåtet. Exempel:
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 Ordna om array Prova!Tanken är att först sortera listan i stigande ordning. Sedan börjar vi poppa element från slutet av listan och infogar dem på rätt plats i listan. Nedan är implementeringen av ovanstående idé -
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 */
Produktion1 8 2 7 3 6 4 5Tidskomplexitet: O(N*logN) eftersom vi använder en sorteringsfunktion.
Hjälputrymme: O(1) eftersom vi inte använder extra utrymme.
Tillvägagångssätt #2: Använda sort()
Sortera den givna listan i stigande ordning Initiera en tom resultatlista Iterera över hälften av de sorterade listindexen: Lägg till elementet från det aktuella indexet och motsvarande element från slutet av listan Om längden på den ursprungliga listan är udda, lägg till mittelementet i resultatlistan Konvertera resultatlistan till en sträng med mellanslagsseparerade heltal
Algoritm
1. Sortera listan med hjälp av sort()-funktionen
C++
2. Initiera en tom resultatlista
3. Gå igenom intervallet för den första halvan av listan
4. Lägg till det i-te elementet i den sorterade listan
5. Lägg till det (-i-1)-te elementet i den sorterade listan
6. Om längden på den ursprungliga listan är udda, lägg till mittelementet i resultatlistan
7. Konvertera resultatlistan till en sträng med funktionen 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 ); } }
Produktion1 8 2 7 3 6 4 5Tidskomplexitet: O(nlogn) på grund av sorteringsoperationen. For-loopen itererar över hälften av listan vilket tar O(n/2) tid. Konverteringen av resultatlistan till en sträng tar O(n) tid. Eftersom O(nlogn) är större än O(n) är den totala tidskomplexiteten O(n*logn).
Auxiliary Space: O(n) eftersom den sorterade listan och resultatlistan båda tar O(n) space. Utrymmet som används av variablerna som används i funktionen är konstant och beror inte på storleken på inmatningslistan.
