#practiceLinkDiv { display: none !important; }Adott egy egész számok listája, rendezze át a listát úgy, hogy váltakozó minimális maximális elemekből álljon csak listaműveletek használatával . A lista első elemének minimálisnak, a másodiknak pedig a maximumnak kell lennie a listában található összes elem közül. Hasonlóképpen a harmadik elem lesz a következő minimális elem, a negyedik elem pedig a következő maximális elem, és így tovább. Extra hely használata nem megengedett. Példák:
Input: [1 3 8 2 7 5 6 4]Recommended Practice Tömb átrendezése Próbáld ki!
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]
Az ötlet az, hogy a listát először növekvő sorrendbe rendezzük. Ezután a lista végéről kezdjük az elemek felbukkanását, és beillesztjük őket a megfelelő helyükre a listában. Alább látható a fenti ötlet megvalósítása -
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>
Kimenet
1 8 2 7 3 6 4 5
Időbeli összetettség: O(N*logN), mivel rendezési függvényt használunk.
Kiegészítő tér: O(1), mivel nem használunk extra helyet.
2. megközelítés: A sort() használata
Adott lista rendezése növekvő sorrendben Üres eredménylista inicializálása A rendezett listaindexek több mint felét iterálja: Az aktuális index elemének hozzáfűzése és a lista végéről a megfelelő elem hozzáfűzése Ha az eredeti lista hossza páratlan a középső elem hozzáfűzése az eredménylistához Az eredménylista konvertálása szóközzel elválasztott egész számokat tartalmazó karakterláncsá
Algoritmus
1. Rendezze a listát a sort() függvény segítségével
2. Inicializáljon egy üres eredménylistát
3. Lapozzon át a lista első felének tartományán
4. Adja hozzá a rendezett lista i-edik elemét
5. Adja hozzá a rendezett lista (-i-1)-edik elemét
6. Ha az eredeti lista hossza páratlan, fűzze hozzá a középső elemet az eredménylistához
7. Alakítsa át az eredménylistát karakterláncsá a join() függvény segítségével
#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));
Kimenet
1 8 2 7 3 6 4 5
Időbonyolultság: O(nlogn) a rendezési művelet miatt. A for ciklus a lista több mint felét iterálja, ami O(n/2) időt vesz igénybe. Az eredménylista sztringgé konvertálása O(n) időt vesz igénybe. Mivel O(nlogn) nagyobb, mint O(n), a teljes időbonyolultság O(n*logn).
Segédtér: O(n), mert a rendezett lista és az eredménylista egyaránt O(n) helyet foglal el. A függvényben használt változók által használt hely állandó, és nem függ a bemeneti lista méretétől.