짝수순으로 오름차순, 홀수순으로 내림차순으로 정렬

n개의 고유한 숫자로 구성된 배열이 제공됩니다. 과제는 모든 짝수에 있는 숫자를 증가하는 순서로, 홀수에 있는 숫자를 내림차순으로 정렬하는 것입니다. 수정된 배열에는 정렬된 짝수 번호와 역 정렬된 홀수 번호가 모두 포함되어야 합니다.

첫 번째 요소는 인덱스가 0이므로 짝수로 배치된 것으로 간주됩니다.

예:

입력: 도착[] = {0 1 2 3 4 5 6 7}
산출: 도착[] = {0 2 4 6 7 5 3 1}
설명:
짝수 요소 : 0 2 4 6
이상한 요소 : 1 3 5 7
짝수 요소를 오름차순으로 정렬:
0 2 4 6
홀수 요소를 내림차순으로 표시:
7 5 3 1

입력: 도착[] = {3 1 2 4 5 9 13 14 12}
산출: {2 3 5 12 13 14 9 4 1}
설명:
짝수 요소 : 3 2 5 13 12
이상한 요소 : 1 4 9 14
짝수 요소를 오름차순으로 정렬:
2 3 5 12 13
홀수 요소를 내림차순으로 표시:
14 9 4 1

[순진한 접근 방식] - O(n Log n) 시간 및 O(n) 공간

아이디어는 간단합니다. 두 개의 보조 배열 evenArr[]과oddArr[]을 각각 생성합니다. 입력 배열을 순회하여 짝수 위치에 있는 모든 요소를 evenArr[]에 넣고 홀수 위치에 있는 요소를 홀수Arr[]에 넣습니다. 그런 다음 evenArr[]을 오름차순으로,oddArr[]을 내림차순으로 정렬합니다. 마지막으로 evenArr[] 및oddArr[]을 복사하여 필요한 결과를 얻습니다.

C++

// Program to separately sort even-placed and odd // placed numbers and place them together in sorted // array. #include    using namespace std; void bitonicGenerator(vector<int>& arr) {  // create evenArr[] and oddArr[]  vector<int> evenArr;  vector<int> oddArr;  // Put elements in oddArr[] and evenArr[] as  // per their position  for (int i = 0; i < arr.size(); i++) {  if (!(i % 2))  evenArr.push_back(arr[i]);  else  oddArr.push_back(arr[i]);  }  // sort evenArr[] in ascending order  // sort oddArr[] in descending order  sort(evenArr.begin() evenArr.end());  sort(oddArr.begin() oddArr.end() greater<int>());  int i = 0;  for (int j = 0; j < evenArr.size(); j++)  arr[i++] = evenArr[j];  for (int j = 0; j < oddArr.size(); j++)  arr[i++] = oddArr[j]; } // Driver Program int main() {  vector<int> arr = { 1 5 8 9 6 7 3 4 2 0 };  bitonicGenerator(arr);  for (int i = 0; i < arr.size(); i++)  cout << arr[i] << ' ';  return 0; }

Java

// Program to separately sort even-placed and odd // placed numbers and place them together in sorted // array. import java.util.*; public class Main {  public static void bitonicGenerator(int[] arr) {    // create evenArr[] and oddArr[]  List<Integer> evenArr = new ArrayList<>();  List<Integer> oddArr = new ArrayList<>();  // Put elements in oddArr[] and evenArr[] as  // per their position  for (int i = 0; i < arr.length; i++) {  if (i % 2 == 0)  evenArr.add(arr[i]);  else  oddArr.add(arr[i]);  }  // sort evenArr[] in ascending order  // sort oddArr[] in descending order  Collections.sort(evenArr);  Collections.sort(oddArr Collections.reverseOrder());  int i = 0;  for (int num : evenArr)  arr[i++] = num;  for (int num : oddArr)  arr[i++] = num;  }  public static void main(String[] args) {  int[] arr = { 1 5 8 9 6 7 3 4 2 0 };  bitonicGenerator(arr);  for (int num : arr)  System.out.print(num + ' ');  } }

Python

# Program to separately sort even-placed and odd # placed numbers and place them together in sorted # array. def bitonic_generator(arr): # create evenArr[] and oddArr[] evenArr = [] oddArr = [] # Put elements in oddArr[] and evenArr[] as # per their position for i in range(len(arr)): if i % 2 == 0: evenArr.append(arr[i]) else: oddArr.append(arr[i]) # sort evenArr[] in ascending order # sort oddArr[] in descending order evenArr.sort() oddArr.sort(reverse=True) i = 0 for num in evenArr: arr[i] = num i += 1 for num in oddArr: arr[i] = num i += 1 # Driver Program arr = [1 5 8 9 6 7 3 4 2 0] bitonic_generator(arr) print(' '.join(map(str arr)))

// Program to separately sort even-placed and odd // placed numbers and place them together in sorted // array. using System; using System.Collections.Generic; using System.Linq; class Program {  static void BitonicGenerator(int[] arr) {    // create evenArr[] and oddArr[]  List<int> evenArr = new List<int>();  List<int> oddArr = new List<int>();  // Put elements in oddArr[] and evenArr[] as  // per their position  for (int i = 0; i < arr.Length; i++) {  if (i % 2 == 0)  evenArr.Add(arr[i]);  else  oddArr.Add(arr[i]);  }  // sort evenArr[] in ascending order  // sort oddArr[] in descending order  evenArr.Sort();  oddArr.Sort((a b) => b.CompareTo(a));  int index = 0;  foreach (var num in evenArr)  arr[index++] = num;  foreach (var num in oddArr)  arr[index++] = num;  }  static void Main() {  int[] arr = { 1 5 8 9 6 7 3 4 2 0 };  BitonicGenerator(arr);  Console.WriteLine(string.Join(' ' arr));  } }

JavaScript

// Program to separately sort even-placed and odd // placed numbers and place them together in sorted // array. function bitonicGenerator(arr) {  // create evenArr[] and oddArr[]  const evenArr = [];  const oddArr = [];  // Put elements in oddArr[] and evenArr[] as  // per their position  for (let i = 0; i < arr.length; i++) {  if (i % 2 === 0)  evenArr.push(arr[i]);  else  oddArr.push(arr[i]);  }  // sort evenArr[] in ascending order  // sort oddArr[] in descending order  evenArr.sort((a b) => a - b);  oddArr.sort((a b) => b - a);  let i = 0;  for (const num of evenArr)  arr[i++] = num;  for (const num of oddArr)  arr[i++] = num; } // Driver Program const arr = [1 5 8 9 6 7 3 4 2 0]; bitonicGenerator(arr); console.log(arr.join(' '));

PHP

// Program to separately sort even-placed and odd // placed numbers and place them together in sorted // array. function bitonicGenerator(&$arr) {  // create evenArr[] and oddArr[]  $evenArr = [];  $oddArr = [];  // Put elements in oddArr[] and evenArr[] as  // per their position  foreach ($arr as $i => $value) {  if ($i % 2 === 0)  $evenArr[] = $value;  else  $oddArr[] = $value;  }  // sort evenArr[] in ascending order  // sort oddArr[] in descending order  sort($evenArr);  rsort($oddArr);  $i = 0;  foreach ($evenArr as $num) {  $arr[$i++] = $num;  }  foreach ($oddArr as $num) {  $arr[$i++] = $num;  } } // Driver Program $arr = [1 5 8 9 6 7 3 4 2 0]; bitonicGenerator($arr); echo implode(' ' $arr);

산출

1 2 3 6 8 9 7 5 4 0

[예상 접근법 - 1] - O(n Log n) 시간과 O(1) 공간

보조 공간을 사용하지 않고도 문제를 해결할 수 있습니다. 아이디어는 첫 번째 절반의 홀수 인덱스 위치를 두 번째 절반의 짝수 인덱스 위치로 바꾼 다음 첫 번째 절반 배열을 오름차순으로 정렬하고 두 번째 절반 배열을 내림차순으로 정렬하는 것입니다.

C++

#include    using namespace std; void bitonicGenerator(vector<int>& arr) {  // first odd index  int i = 1;  // last index  int n = arr.size();  int j = n - 1;  // if last index is odd  if (j % 2 != 0)    // decrement j to even index  j--;  // swapping till half of array  while (i < j) {  swap(arr[i] arr[j]);  i += 2;  j -= 2;  }  // Sort first half in increasing  sort(arr.begin() arr.begin() + (n + 1) / 2);  // Sort second half in decreasing  sort(arr.begin() + (n + 1) / 2 arr.end() greater<int>()); } // Driver Program int main() {  vector<int> arr = { 1 5 8 9 6 7 3 4 2 0 };  bitonicGenerator(arr);  for (int i = 0; i < arr.size(); i++)  cout << arr[i] << ' ';  return 0; }

Java

import java.util.Arrays; class BitonicGenerator {  public static void bitonicGenerator(int[] arr) {    // first odd index  int i = 1;  // last index  int n = arr.length;  int j = n - 1;  // if last index is odd  if (j % 2 != 0)    // decrement j to even index  j--;  // swapping till half of array  while (i < j) {  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  i += 2;  j -= 2;  }  // Sort first half in increasing order  Arrays.sort(arr 0 (n + 1) / 2);  // Sort second half in decreasing order  Arrays.sort(arr (n + 1) / 2 n);  reverse(arr (n + 1) / 2 n);  }  private static void reverse(int[] arr int start int end) {  end--;  while (start < end) {  int temp = arr[start];  arr[start] = arr[end];  arr[end] = temp;  start++;  end--;  }  }  // Driver Program  public static void main(String[] args) {  int[] arr = {1 5 8 9 6 7 3 4 2 0};  bitonicGenerator(arr);  for (int num : arr) {  System.out.print(num + ' ');  }  } }

Python

def bitonic_generator(arr): # first odd index i = 1 # last index n = len(arr) j = n - 1 # if last index is odd if j % 2 != 0: # decrement j to even index j -= 1 # swapping till half of array while i < j: arr[i] arr[j] = arr[j] arr[i] i += 2 j -= 2 # Sort first half in increasing arr[:(n + 1) // 2] = sorted(arr[:(n + 1) // 2]) # Sort second half in decreasing arr[(n + 1) // 2:] = sorted(arr[(n + 1) // 2:] reverse=True) # Driver Program arr = [1 5 8 9 6 7 3 4 2 0] bitonic_generator(arr) print(' '.join(map(str arr)))

// Function to generate a bitonic sequence using System; using System.Collections.Generic; using System.Linq; class Program {  static void BitonicGenerator(List<int> arr)  {  // first odd index  int i = 1;  // last index  int n = arr.Count;  int j = n - 1;  // if last index is odd  if (j % 2 != 0)    // decrement j to even index  j--;  // swapping till half of array  while (i < j)  {  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  i += 2;  j -= 2;  }  // Sort first half in increasing  arr.Sort(0 (n + 1) / 2);  // Sort second half in decreasing  arr.Sort((n + 1) / 2 n - (n + 1) / 2 Comparer<int>.Create((x y) => y.CompareTo(x)));  }  // Driver Program  static void Main()  {  List<int> arr = new List<int> { 1 5 8 9 6 7 3 4 2 0 };  BitonicGenerator(arr);  Console.WriteLine(string.Join(' ' arr));  } }

JavaScript

// Function to generate a bitonic sequence function bitonicGenerator(arr) {    // first odd index  let i = 1;  // last index  let n = arr.length;  let j = n - 1;  // if last index is odd  if (j % 2 !== 0)  // decrement j to even index  j--;  // swapping till half of array  while (i < j) {  [arr[i] arr[j]] = [arr[j] arr[i]];  i += 2;  j -= 2;  }  // Sort first half in increasing  arr.sort((a b) => a - b);  // Sort second half in decreasing  arr.slice((n + 1) / 2).sort((a b) => b - a); } // Driver Program let arr = [1 5 8 9 6 7 3 4 2 0]; bitonicGenerator(arr); console.log(arr.join(' '));

산출

1 2 3 6 8 9 7 5 4 0

참고: 위의 Python 및 JS 코드에는 추가 공간이 필요한 것 같습니다. 여러분의 생각과 대체 구현에 대해 의견을 보내주세요.

[예상 접근법 - 2] - O(n Log n) 시간과 O(1) 공간

O(1) 보조 공간의 문제를 해결하는 또 다른 효율적인 접근 방식은 다음과 같습니다. 음의 곱셈 사용 .

관련된 단계는 다음과 같습니다.

짝수 인덱스에 있는 모든 요소에 -1을 곱합니다.
전체 배열을 정렬합니다. 이런 식으로 우리는 이제 음수이므로 시작 부분에 짝수 인덱스를 모두 얻을 수 있습니다.
이제 이러한 요소의 부호를 되돌립니다.
그런 다음 짝수를 포함하는 배열의 전반부를 뒤집어서 오름차순으로 만듭니다.
그런 다음 배열의 나머지 절반을 뒤집어 홀수 번째 숫자를 내림차순으로 만듭니다.

메모: 이 방법은 배열의 모든 요소가 음수가 아닌 경우에만 적용 가능합니다.

위 접근 방식의 예시는 다음과 같습니다.

주어진 배열을 보자: 도착[] = {0 1 2 3 4 5 6 7}
짝수 배치된 요소에 -1을 곱한 후의 배열: arr[] = {0 1 -2 3 -4 5 -6 7}
정렬 후 배열: arr[] = {-6 -4 -2 0 1 3 5 7}
음수 값을 되돌린 후의 배열: arr[] = {6 4 2 0 1 3 5 7}
배열의 전반부를 뒤집은 후: arr[] = {0 2 4 6 1 3 5 7}
배열의 후반부를 뒤집은 후: arr[] = {0 2 4 6 7 5 3 1}

위의 접근 방식에 대한 코드는 다음과 같습니다.

C++

#include    using namespace std; void bitonicGenerator(vector<int>& arr) {  // Making all even placed index   // element negative  for (int i = 0; i < arr.size(); i++) {  if (i % 2==0)  arr[i] = -1 * arr[i];  }    // Sorting the whole array  sort(arr.begin() arr.end());    // Finding the middle value of   // the array  int mid = (arr.size() - 1) / 2;    // Reverting the changed sign  for (int i = 0; i <= mid; i++) {  arr[i] = -1 * arr[i];  }    // Reverse first half of array  reverse(arr.begin() arr.begin() + mid + 1);    // Reverse second half of array  reverse(arr.begin() + mid + 1 arr.end()); } // Driver Program int main() {  vector<int> arr = { 1 5 8 9 6 7 3 4 2 0 };  bitonicGenerator(arr);  for (int i = 0; i < arr.size(); i++)  cout << arr[i] << ' ';  return 0; }

Java

import java.util.Arrays; import java.util.List; public class BitonicGenerator {  public static void bitonicGenerator(List<Integer> arr) {    // Making all even placed index   // element negative  for (int i = 0; i < arr.size(); i++) {  if (i % 2 == 0)  arr.set(i -1 * arr.get(i));  }    // Sorting the whole array  Collections.sort(arr);    // Finding the middle value of   // the array  int mid = (arr.size() - 1) / 2;    // Reverting the changed sign  for (int i = 0; i <= mid; i++) {  arr.set(i -1 * arr.get(i));  }    // Reverse first half of array  Collections.reverse(arr.subList(0 mid + 1));    // Reverse second half of array  Collections.reverse(arr.subList(mid + 1 arr.size()));  }  // Driver Program  public static void main(String[] args) {  List<Integer> arr = Arrays.asList(1 5 8 9 6 7 3 4 2 0);  bitonicGenerator(arr);  for (int i : arr)  System.out.print(i + ' ');  } }

Python

def bitonic_generator(arr): # Making all even placed index  # element negative for i in range(len(arr)): if i % 2 == 0: arr[i] = -1 * arr[i] # Sorting the whole array arr.sort() # Finding the middle value of  # the array mid = (len(arr) - 1) // 2 # Reverting the changed sign for i in range(mid + 1): arr[i] = -1 * arr[i] # Reverse first half of array arr[:mid + 1] = reversed(arr[:mid + 1]) # Reverse second half of array arr[mid + 1:] = reversed(arr[mid + 1:]) # Driver Program arr = [1 5 8 9 6 7 3 4 2 0] bitonic_generator(arr) print(' '.join(map(str arr)))

using System; using System.Collections.Generic; using System.Linq; class BitonicGenerator {  public static void BitonicGeneratorMethod(List<int> arr) {    // Making all even placed index   // element negative  for (int i = 0; i < arr.Count; i++) {  if (i % 2 == 0)  arr[i] = -1 * arr[i];  }    // Sorting the whole array  arr.Sort();    // Finding the middle value of   // the array  int mid = (arr.Count - 1) / 2;    // Reverting the changed sign  for (int i = 0; i <= mid; i++) {  arr[i] = -1 * arr[i];  }    // Reverse first half of array  arr.Take(mid + 1).Reverse().ToList().CopyTo(arr);    // Reverse second half of array  arr.Skip(mid + 1).Reverse().ToList().CopyTo(arr mid + 1);  }  // Driver Program  public static void Main() {  List<int> arr = new List<int> { 1 5 8 9 6 7 3 4 2 0 };  BitonicGeneratorMethod(arr);  Console.WriteLine(string.Join(' ' arr));  } }

JavaScript

function bitonicGenerator(arr) {    // Making all even placed index   // element negative  for (let i = 0; i < arr.length; i++) {  if (i % 2 === 0)  arr[i] = -1 * arr[i];  }    // Sorting the whole array  arr.sort((a b) => a - b);    // Finding the middle value of   // the array  const mid = Math.floor((arr.length - 1) / 2);    // Reverting the changed sign  for (let i = 0; i <= mid; i++) {  arr[i] = -1 * arr[i];  }    // Reverse first half of array  arr.slice(0 mid + 1).reverse().forEach((val index) => arr[index] = val);    // Reverse second half of array  arr.slice(mid + 1).reverse().forEach((val index) => arr[mid + 1 + index] = val); } // Driver Program let arr = [1 5 8 9 6 7 3 4 2 0]; bitonicGenerator(arr); console.log(arr.join(' '));

산출

1 2 3 6 8 9 7 5 4 0

퀴즈 만들기