#practiceLinkDiv { 表示: なし !重要; }整数のリストが与えられた場合、最小値と最大値の要素が交互に並ぶようにリストを再配置します。 リスト操作のみを使用する 。リストの最初の要素はリストに存在するすべての要素の最小値、2 番目の要素は最大値である必要があります。同様に、3 番目の要素が次の最小要素となり、4 番目の要素が次の最大要素となり、以下同様となります。余分なスペースの使用は許可されません。例:
Input: [1 3 8 2 7 5 6 4]Recommended Practice 配列の再配置 試してみてください!
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]
最初にリストを昇順に並べ替えることが目的です。次に、リストの末尾から要素をポップし始め、リスト内の正しい位置に要素を挿入します。以下は上記のアイデアの実装です –
C++
// C++ program to rearrange a given list such that it // consists of alternating minimum maximum elements #include
// 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 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# 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 */
<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(it0 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: sort() を使用する
指定されたリストを昇順でソートします。 空の結果リストを初期化します。 ソートされたリストのインデックスの半分を繰り返します。 現在のインデックスから要素を追加し、リストの末尾から対応する要素を追加します。 元のリストの長さが奇数の場合、中間の要素を結果リストに追加します。 結果リストをスペースで区切られた整数の文字列に変換します。
アルゴリズム
1. sort() 関数を使用してリストを並べ替えます。
2. 空の結果リストを初期化する
3. リストの前半の範囲をループします。
4. ソートされたリストの i 番目の要素を追加します。
5. ソートされたリストの (-i-1) 番目の要素を追加します。
6. 元のリストの長さが奇数の場合は、中央の要素を結果リストに追加します。
7. join() 関数を使用して結果リストを文字列に変換します。
#include
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)); } }
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))
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); } }
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) スペースを必要とするためです。関数で使用される変数によって使用されるスペースは一定であり、入力リストのサイズには依存しません。