Belirli bir listeyi, değişen minimum maksimum öğelerden oluşacak şekilde yeniden düzenleyin
GfG Practice'de deneyin 
#practiceLinkDiv { görüntü: yok !önemli; }
#practiceLinkDiv { görüntü: yok !önemli; } Bir tamsayı listesi verildiğinde, listeyi alternatif minimum maksimum öğelerden oluşacak şekilde yeniden düzenleyin yalnızca liste işlemlerini kullanma . Listenin ilk elemanı listedeki tüm elemanların minimum, ikinci elemanı ise maksimum olmalıdır. Benzer şekilde üçüncü eleman bir sonraki minimum eleman olacak ve dördüncü eleman bir sonraki maksimum eleman olacak ve bu şekilde devam edecek. Ekstra alan kullanımına izin verilmez. Örnekler:
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 Dizi yeniden düzenleniyor Deneyin!Buradaki fikir, önce listeyi artan düzende sıralamaktır. Daha sonra listenin sonundan elemanları çıkarmaya başlıyoruz ve onları listedeki doğru konumlarına yerleştiriyoruz. Aşağıda yukarıdaki fikrin uygulanması yer almaktadır -
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 */
Çıkış1 8 2 7 3 6 4 5Zaman Karmaşıklığı: O(N*logN) çünkü bir sıralama işlevi kullanıyoruz.
Yardımcı Alan: O(1) çünkü ekstra alan kullanmıyoruz.
Yaklaşım#2: sort()'u kullanma
Verilen listeyi artan düzende sıralayın Boş bir sonuç listesi başlatın Sıralanan liste indekslerinin yarısından fazlasını yineleyin: Öğeyi geçerli dizinden ve karşılık gelen öğeyi listenin sonundan ekleyin Orijinal listenin uzunluğu tek ise ortadaki öğeyi sonuç listesine ekleyin Sonuç listesini boşlukla ayrılmış tamsayılarla bir dizeye dönüştürün
Algoritma
1. sort() işlevini kullanarak listeyi sıralayın
C++
2. Boş bir sonuç listesini başlatın
3. Listenin ilk yarısındaki aralıkta dolaşın
4. Sıralanan listenin i'inci öğesini ekleyin
5. Sıralanan listenin (-i-1)'inci elemanını ekleyin
6. Orijinal listenin uzunluğu tek ise ortadaki öğeyi sonuç listesine ekleyin
7. join() işlevini kullanarak sonuç listesini bir dizeye dönüştürünJava#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 ); } }
Çıkış1 8 2 7 3 6 4 5Zaman Karmaşıklığı: Sıralama işlemi nedeniyle O(nlogn). For döngüsü, O(n/2) zaman alan listenin yarısından fazlasını yineler. Sonuç listesinin bir dizeye dönüştürülmesi O(n) zaman alır. O(nlogn) O(n)'den büyük olduğundan genel zaman karmaşıklığı O(n*logn) olur.
Yardımcı Alan: O(n) çünkü sıralanmış liste ve sonuç listesi O(n) alanı kaplar. Fonksiyonda kullanılan değişkenlerin kullandığı alan sabittir ve giriş listesinin boyutuna bağlı değildir.
