Mums duota n skirtingų skaičių masyvas. Užduotis – visus lyginius skaičius surūšiuoti didėjančia, o nelyginius – mažėjimo tvarka. Modifikuotame masyve turi būti visi surūšiuoti lyginės eilės skaičiai, po kurių seka atvirkščiai surūšiuoti nelyginiai skaičiai.
Atminkite, kad pirmasis elementas laikomas lyginiu, nes jo indeksas yra 0.
Pavyzdžiai:
Įvestis: arr[] = {0 1 2 3 4 5 6 7}
Išvestis: arr[] = {0 2 4 6 7 5 3 1}
Paaiškinimas:
Lyginės vietos elementai: 0 2 4 6
Nelyginiai elementai: 1 3 5 7
Lygios vietos elementai didėjančia tvarka:
0 2 4 6
Nelyginės vietos elementai mažėjimo tvarka:
7 5 3 1
Įvestis: arr[] = {3 1 2 4 5 9 13 14 12}
Išvestis: {2 3 5 12 13 14 9 4 1}
Paaiškinimas:
Lyginės vietos elementai: 3 2 5 13 12
Nelyginiai elementai: 1 4 9 14
Lygios vietos elementai didėjančia tvarka:
2 3 5 12 13
Nelyginės vietos elementai mažėjimo tvarka:
14 9 4 1
[Naive Approach] – O(n Log n) laikas ir O(n) erdvė
Idėja paprasta. Sukuriame atitinkamai du pagalbinius masyvus evenArr[] ir oddArr[]. Perkeliame įvesties masyvą ir visus lygioje vietoje esančius elementus dedame į evenArr[], o nelyginius elementus – į oddArr[]. Tada rūšiuojame evenArr[] didėjančia ir oddArr[] mažėjimo tvarka. Galiausiai nukopijuokite evenArr[] ir oddArr[], kad gautumėte reikiamą rezultatą.
C++// Program to separately sort even-placed and odd // placed numbers and place them together in sorted // array. #include
// 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 + ' '); } }
# 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)); } }
// 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(' '));
// 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);
Išvestis
1 2 3 6 8 9 7 5 4 0
[Numatomas artėjimas – 1] – O(n Log n) laikas ir O(1) erdvė
Problemą taip pat galima išspręsti nenaudojant pagalbinės erdvės. Idėja yra sukeisti pirmosios pusės nelygines indekso pozicijas su antrosios pusės lyginėmis indekso pozicijomis, o tada surūšiuoti pirmąją masyvo pusę didėjančia tvarka, o antrąją pusę – mažėjimo tvarka.
C++#include
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 + ' '); } } }
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)); } }
// 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(' '));
Išvestis
1 2 3 6 8 9 7 5 4 0
Pastaba: atrodo, kad aukščiau nurodytiems Python ir JS kodams reikia papildomos vietos. Praneškite mums komentaruose apie savo mintis ir bet kokius alternatyvius įgyvendinimus.
[Numatomas artėjimas – 2] – O(n Log n) laikas ir O(1) erdvė
Kitas veiksmingas būdas išspręsti problemą O(1) pagalbinėje erdvėje yra Naudojant neigiamą daugybą .
Veiksmai yra tokie:
- Padauginkite visus lyginio indekso elementus iš -1.
- Rūšiuoti visą masyvą. Tokiu būdu mes galime gauti visus lyginius indeksus pradžioje, nes dabar jie yra neigiami skaičiai.
- Dabar grąžinkite šių elementų ženklą.
- Po to apverskite pirmąją masyvo pusę, kurioje yra lyginis skaičius, kad jis būtų didėjančia tvarka.
- Tada apverskite likusią masyvo pusę, kad nelyginiai skaičiai būtų išdėstyti mažėjančia tvarka.
Pastaba: Šis metodas taikomas tik tuo atveju, jei visi masyvo elementai yra neneigiami.
Aukščiau pateikto metodo pavyzdys:
Tegul pateiktas masyvas: arr[] = {0 1 2 3 4 5 6 7}
Masyvas padauginus iš -1 iki lyginių elementų: arr[] = {0 1 -2 3 -4 5 -6 7}
Masyvas po rūšiavimo: arr[] = {-6 -4 -2 0 1 3 5 7}
Masyvas grąžinus neigiamas reikšmes: arr[] = {6 4 2 0 1 3 5 7}
Apvertus pirmąją masyvo pusę: arr[] = 0 2 4 6 1 3 5 7}
Pakeitus antrąją masyvo pusę: arr[] = 0 2 4 6 7 5 3 1}
Žemiau yra pirmiau nurodyto metodo kodas:
C++#include
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 + ' '); } }
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)); } }
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(' '));
Išvestis
1 2 3 6 8 9 7 5 4 0
Sukurti viktoriną