指定されたリストを、最小最大要素が交互に並ぶように再配置します。
GfG Practice で試してみる 
#practiceLinkDiv { 表示: なし !重要; }
#practiceLinkDiv { 表示: なし !重要; } 整数のリストが与えられた場合、最小値と最大値の要素が交互に並ぶようにリストを再配置します。 リスト操作のみを使用する 。リストの最初の要素はリストに存在するすべての要素の最小値、2 番目の要素は最大値である必要があります。同様に、3 番目の要素が次の最小要素となり、4 番目の要素が次の最大要素となり、以下同様となります。余分なスペースの使用は許可されません。例:
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++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 */
出力1 8 2 7 3 6 4 5時間計算量: ソート関数を使用しているため、O(N*logN) になります。
補助スペース: 余分なスペースを使用していないため、O(1)。
アプローチ#2: sort() を使用する
指定されたリストを昇順でソートします。 空の結果リストを初期化します。 ソートされたリストのインデックスの半分を繰り返します。 現在のインデックスから要素を追加し、リストの末尾から対応する要素を追加します。 元のリストの長さが奇数の場合、中間の要素を結果リストに追加します。 結果リストをスペースで区切られた整数の文字列に変換します。
アルゴリズム
1. sort() 関数を使用してリストを並べ替えます。
C++
2. 空の結果リストを初期化する
3. リストの前半の範囲をループします。
4. ソートされたリストの i 番目の要素を追加します。
5. ソートされたリストの (-i-1) 番目の要素を追加します。
6. 元のリストの長さが奇数の場合は、中央の要素を結果リストに追加します。
7. 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 ); } }
出力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) スペースを必要とするためです。関数で使用される変数によって使用されるスペースは一定であり、入力リストのサイズには依存しません。
