We krijgen een array van n verschillende getallen. De taak is om alle even geplaatste getallen in stijgende en oneven geplaatste getallen in afnemende volgorde te sorteren. De gewijzigde array moet alle gesorteerde even geplaatste getallen bevatten, gevolgd door omgekeerd gesorteerde oneven geplaatste getallen.
Merk op dat het eerste element als gelijk geplaatst wordt beschouwd vanwege de index 0.
Voorbeelden:
Invoer: arr[] = {0 1 2 3 4 5 6 7}
Uitgang: arr[] = {0 2 4 6 7 5 3 1}
Uitleg:
Gelijkmatige elementen: 0 2 4 6
Elementen op vreemde plaatsen: 1 3 5 7
Gelijkmatige elementen in oplopende volgorde:
0 2 4 6
Odd-Place-elementen in afnemende volgorde:
7 5 3 1
Invoer: arr[] = {3 1 2 4 5 9 13 14 12}
Uitgang: {2 3 5 12 13 14 9 4 1}
Uitleg:
Gelijkmatige elementen: 3 2 5 13 12
Elementen op vreemde plaatsen: 1 4 9 14
Gelijkmatige elementen in oplopende volgorde:
2 3 5 12 13
Odd-Place-elementen in afnemende volgorde:
14 9 4 1
[Naïeve benadering] - O(n Log n) Tijd en O(n) Ruimte
Het idee is eenvoudig. We maken respectievelijk twee hulparrays evenArr[] en oddArr[]. We doorkruisen de invoerarray en plaatsen alle even geplaatste elementen in evenArr[] en oneven geplaatste elementen in oddArr[]. Vervolgens sorteren we evenArr[] in oplopende volgorde en onevenArr[] in aflopende volgorde. Kopieer ten slotte evenArr[] en oddArr[] om het gewenste resultaat te krijgen.
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);
Uitvoer
1 2 3 6 8 9 7 5 4 0
[Verwachte aanpak - 1] - O(n Log n) Tijd en O(1) Ruimte
Het probleem kan ook worden opgelost zonder het gebruik van hulpruimte. Het idee is om de eerste helft van de oneven indexposities te verwisselen met de tweede helft van de even indexposities en vervolgens de eerste halve array in oplopende volgorde te sorteren en de tweede halve array in afnemende volgorde.
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(' '));
Uitvoer
1 2 3 6 8 9 7 5 4 0
Opmerking: de bovenstaande Python- en JS-codes lijken extra ruimte nodig te hebben. Laat ons in de reacties weten wat uw gedachten en eventuele alternatieve implementaties zijn.
[Verwachte aanpak - 2] - O(n Log n) Tijd en O(1) Ruimte
Een andere efficiënte benadering om het probleem in de O(1)-hulpruimte op te lossen is door Negatieve vermenigvuldiging gebruiken .
De betrokken stappen zijn als volgt:
- Vermenigvuldig alle elementen op de even geplaatste index met -1.
- Sorteer de hele array. Op deze manier kunnen we alle indexen in het begin gelijk plaatsen, aangezien het nu negatieve getallen zijn.
- Draai nu het teken van deze elementen om.
- Hierna wordt de eerste helft van de array, die een even geplaatst getal bevat, omgedraaid om deze in oplopende volgorde te maken.
- En draai dan de rest van de array om om oneven geplaatste getallen in afnemende volgorde te maken.
Opmerking: Deze methode is alleen toepasbaar als alle elementen in de array niet-negatief zijn.
Een illustratief voorbeeld van de bovenstaande aanpak:
Laat gegeven array: arr[] = {0 1 2 3 4 5 6 7}
Array na vermenigvuldiging met -1 tot even geplaatste elementen: arr[] = {0 1 -2 3 -4 5 -6 7}
Array na sorteren: arr[] = {-6 -4 -2 0 1 3 5 7}
Array na het terugdraaien van negatieve waarden: arr[] = {6 4 2 0 1 3 5 7}
Na het omkeren van de eerste helft van de array: arr[] = {0 2 4 6 1 3 5 7}
Na het omkeren van de tweede helft van de array: arr[] = {0 2 4 6 7 5 3 1}
Hieronder vindt u de code voor de bovenstaande aanpak:
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(' '));
Uitvoer
1 2 3 6 8 9 7 5 4 0
Quiz maken