#practiceLinkDiv { 표시: 없음 !중요; }정수 목록이 주어지면 교대로 최소 최대 요소로 구성되도록 목록을 재정렬합니다. 목록 작업만 사용 . 목록의 첫 번째 요소는 최소값이어야 하고 두 번째 요소는 목록에 있는 모든 요소 중 최대값이어야 합니다. 마찬가지로 세 번째 요소는 다음 최소 요소가 되고 네 번째 요소는 다음 최대 요소가 됩니다. 추가 공간 사용은 허용되지 않습니다. 예:
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) 공간을 차지하기 때문입니다. 함수에 사용되는 변수가 사용하는 공간은 일정하며 입력 목록의 크기에 의존하지 않습니다.